Code More Create

Appearance

Return to top

最长递增子序列

动态规划的难点本来就在于寻找正确的状态转移方程，借助经典的「最长递增子序列问题」来讲一讲设计动态规划的通用技巧：数学归纳思想。

最长递增子序列这个问题，首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么？

我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

根据这个定义，我们就可以推出 base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。

根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 建立dp数组，表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // base case,以nums[i]结尾的最长递增子序列起码包括它本身
        Arrays.fill(dp,1);
        // 遍历nums数组，计算每个dp的值
        for(int i = 0;i<nums.length;i++){
            // 遍历走过数的所有数
            for(int j = 0; j < i; j++){
                // 如果之前的某个数小于当前这个数，则在其dp[j]的基础上加1，与当前dp[i]进行比较，取大数
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        // 取出dp数组中的最大数
        int res = 0;
        for(int i = 0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}