【常见笔试面试算法题12续集三】动态规划算法案例分析3 LIS练习题（最长上升子序列）

加qq1126137994 一起学习更多技术！！！

这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。

给定一个序列arr及它的长度n(长度小于等于500)，请返回LIS的长度。

测试样例：
[2,1,5,3,6,4,8,9,7],9
返回：5

分析思路：化简到子问题，那么这道题应该是化简到求该序列长度的前1,2,3,4,5,6…..n个数的最长上升子序列问题

那么同样是开辟一个数组dp[n] 这里开辟的是数组还是矩阵，是根据实际情况而来。那么dp[i]就代表必须以arr[i]结尾的情况下，arr[0….i]的最长上升子序列的长度。

由上图的分析可知：
dp[0]=1;
dp[1] 取决于arr[1]是否大于arr[0] 本题是不大于，所以dp[1]=1;
dp[2]取决于arr[2]是否大于arr[j]（j=0~1），大于arr[j]的话，那么就取dp[j]+1的最大值
dp[3]取决于arr[3]是否大于arr[j]（j=0~2），大于arr[j]的话，那么就取dp[j]+1的最大值
dp[4]取决于arr[4]是否大于arr[j]（j=0~3），大于arr[j]的话，那么就取dp[j]+1的最大值

那么dp[i]的表达式就应该是：
dp[i]=max{dp[j]+1(j=0~(i-1)),且arr[i]>arr[j]}

由以上分析，可写程序如下：

class LongestIncreasingSubsequence {
public:
    int getLIS(vector<int> A, int n) {
        // write code here
        int dp[n];
        /* 初始化dp */
        for(int i=0;i<n;i++)
        {
            dp[i]=1;
        }
        int Max=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(A[i]>A[j])
                {
                    //注意dp[j]+1这个表达式只能放到判断语句里面，这样才不会改变它的值（只做判断），
                    //如果改变了dp[j]的值，将会影响下一次循环的计算
                    if((dp[j]+1)>dp[i])    
                    dp[i]=dp[j]+1;
                }

            }
            /* 外部每循环一次，则求得了dp[i]的值，选出每次循环后得到的最大值，就是最终需要返回的值 */
             if(dp[i]>Max)
                    Max=dp[i];;
        }
        return Max;
    }
};

动态规划的思想！！！化整体为0,1,2….先计算子问题，再合并计算整体问题！！！