LeetCode 300：最长递增子序列

小半 • 2023年2月3日上午10:51 • 技术随笔 • 阅读 213

链接

注意：

这里的子序列可以不连续 ！
要递增！

思路：动态规划（dp table）

模板：

动态规划的核⼼设计思想是数学归纳法;

如想证明⼀个数学结论，那么我们先假设这个结论在 k < n 时成⽴，然后根据这个假设，想办法推导证明出 k = n 的时候此结论也成⽴。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成⽴。

设计动态规划算法，不是需要⼀个 dp 数组吗？可以假设 dp[0…i-1] 都已经被算出来了，然后问：怎么通过这些结果算出 dp[i]？

dp数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增⼦序列的长度；

base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最⻓递增⼦序列起码要包含它⾃⼰。

根据这个定义，最终数组的结果（⼦序列的最⼤⻓度）应该是 dp 数组中的最⼤值：
用for遍历每个元素作为结尾对应的最大自增子序列的长度，选出最大；

注意：并不是 i 越大，其子序列长度就越大！

假设已经知道了 dp[0…4] 的所有结果，如何通过这些已知结果推出 dp[5] ？
如：

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

nums[5] 前⾯有哪些元素小于 nums[5]？用for 循环比较⼀波就能把这些元素找出来。
以这些元素为结尾的最⻓递增⼦序列的⻓度是多少？回顾⼀下我们对 dp 数组的定义，它记录的正是以每个元素为末尾的最⻓递增⼦序列的⻓度。

例中nums[0] 和 nums[4] 都是小于 nums[5] 的，然后对比 dp[0] 和 dp[4] 的值，我们让 nums[5] 和更长的递增⼦序列结合，得出 dp[5] = 2+1=3 ；

总结：
1.明确 dp 数组的定义。这⼀步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。

2.根据 dp 数组的定义，运⽤数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，⼀旦这⼀步完成，整个题目基本就解决了。

Java实现：

dp定义是 dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度；
状态就是dp数组的索引/值

class Solution {
    public int lengthOfLIS(int[] nums) {
        int dp[]=new int[nums.length];
        Arrays.fill(dp,1); // 每个位置至少长度为1
        for(int i=0;i<nums.length;i++){ 
            for(int j=0;j<i;j++){ // 遍历num[i]之前的所有元素 
            // 找出所有小于nums[i]的数，并找到最大值，最大值+1 ，就是dp[i]
                if(nums[i]>nums[j]){  
                    dp[i]=Math.max(dp[i],dp[j]+1);  
                }
            }
        }
        
        int res=-1;
        for(int i=0;i<nums.length;i++){
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}