dp：子序列，最长递增子序列，最长连续递增子序列，最长重复子数组，最长公共子序列

最长重复子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 104

思路

1. 确定dp数组及其下标含义：dp[i] 代表 i 之前包括 i 的最长递增子序列

2. 递推公式：dp[i] 为 j 从 0 到 i - 1 各个位置的最长递增子序列 + 1（如果 i 位置还是递增）
   即if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)， 这里取最大值是为了，取dp[j] + 1的最大值

3. 初始化：每一个 i 都是长度为1 的递增子序列

4. 确定遍历顺序：dp[i] 是由 0 - i - 1 遍历而来，所以必然是从前往后

5. 举例推导

代码

    public int lengthOfLIS(int[] nums) {
    if(nums.length == 1) return 1;
    int[] dp = new int[nums.length + 1];
    Arrays.fill(dp, 1);
    int result = 0;
    for(int i = 1; i < nums.length; i++) {
        for(int j = 0; j < i; j++) {
            if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        if(result < dp[i])  result = dp[i];
    }
    return result;
    }

最长连续递增子序列

https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：

0 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9‘

思路

1. 确定dp数组及其下标含义：dp[i] 代表 i 结尾的连续递增子序列的长度
2. 推导dp方程：如果nums[i + 1] > nums[i]，那么以dp[i + 1] = dp[i] + 1
3. 初始化：dp[0] = 1;
4. 遍历顺序：从前往后
5. 举例推导

代码

    public int findLengthOfLCIS(int[] nums) {
    if(nums.length == 0) return 0;
    int[] dp = new int[nums.length + 1];
    Arrays.fill(dp, 1);
    int max = 1;
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > nums[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        }
        if(dp[i] > max) max = dp[i];
    }
    return max;
    }

此题当然可以滑动窗口简化，因为每一项dp只依赖上一项

    public int findLengthOfLCIS(int[] nums) {
    if(nums.length == 0) return 0;
    int max = 1;
    int pre = 1;
    for(int i = 1; i < nums.length; i++) {
        int cur = 1;
        if(nums[i] > nums[i - 1]) {
            cur += pre;
        }
        pre = cur;
        if(cur > max) max = cur;
    }
    return max;
    }

区别

上一题和此题的区别在于，递增子序列是否允许不连续
不连续，则需要在前面所有索引里找到最大的递增子序列
连续，则只需要找上一个值即可

最长重复子数组

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

思路

1. 确定dp数组及其下标含义：表示以 i - 1 ， j - 1 结尾的A,B数组，最长重复子序列为dp[i][j]
   弄清楚为什么dp[i][j]代表的是到 i-1 , j-1 的下标的最长子串，而不是 i，j
   因为 dp[i][j] 依赖于 dp[i - 1][j - 1]
   所以对于下标0来说，dp[1][1]就可以代表下标0，依赖于dp[0][0]
   而如果直接代表 i,j 那么对于下标0来说,dp[0][0] 才代表下标0，而他依赖于dp[-1][-1]
   如果要避免dp[-1][-1]越界，就需要考虑更多的边界问题

2. 推导dp方程： 根据dp数组定义，所以dp[i][j]只能由dp[i - 1][j - 1]求出 ，所以
   dp[i][j] = dp[i - 1][j - 1] + 1

3. 初始化:dp[i][0], dp[0][j]都应该为0，长度为0没有重复子序列

4. 遍历顺序：先A还是先B无影响，所以都行，

5. 举例推导dp数组

代码

    public int findLength(int[] nums1, int[] nums2) {
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    int max = 0;
    for(int i = 1; i <= nums1.length; i++) {
        for(int j = 1; j <= nums2.length; j++) {
            if(nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            if(max < dp[i][j]) max = dp[i][j];
        }
    }
    return max;
    }

滚动数组简化，因为dp[i][j] 依赖于dp[i -1 ][j - 1] 即当前这一行依赖于上一行，
所以可以使用一维数组来存储

• 同时要倒序遍历 j ，因为 dp[j] 依赖于 dp[j - 1] 所以倒序遍历就不会覆盖前面的结果，而正序遍历则从 j - 1 推到 j 会覆盖原来的数据
• nums2[j] != nums1[i] 时需要 dp[j] = 0， 因为要不影响到下一个数字，所以这一组数据的长度为0

    public int findLength(int[] nums1, int[] nums2) {
    int[] dp = new int[nums1.length + 1];
    int max = 0;
    for(int i = 1; i <= nums1.length; i++) {
        for(int j = nums2.length; j >= 1; j--) {
            if(nums1[i - 1] == nums2[j - 1]) {
                dp[j] = dp[j - 1] + 1;
            }else {
                dp[j] = 0;
            }
            if(max < dp[j]) max = dp[j];
        }
    }
    return max;
    }

最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:

1 <= text1.length <= 1000
1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

思路

1. 确定dp数组及其下标含义：dp[i][j] 表示从0- i-1 和 0 - j-1的最长公共子序列长度

2. 推导dp数组：
   可以分两种情况，text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
   要求公共子序列，那公共子序列中所有的字母必然都都来自s1与s2中。那我们我们就可以反过来说，s1和s2的中的字母要么就在公共子序列中，要么不在公共子序列中。
   s1[i] == s2[j] 则表示在，所以当前结果就等于之前没进来的字符串结果+1
   即dp[i][j] = dp[i - 1][j - 1] + 1;
   s1[i] != s2[j] 则表示当前至少有一个不在公共子序列中（要么s1[i]不在，要么s2[j]不在，要么都不在，所以当前结果就等于之前结果中最大的一个）
   即dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

3. 初始化：dp[i][0] = 0, dp[0][j] = 0

4. 确定遍历顺序：从左至右从上至下

5. 举例推导：dp[text1.length()][text2.length()]为答案

代码

    public int longestCommonSubsequence(String s1, String s2) {
    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    for(int i = 1; i <= s1.length(); i++) {
        for(int j = 1; j <= s2.length(); j++) {
            if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[s1.length()][s2.length()];
    }

总结

• 最长递增子序列（不连续的递增）if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

• 最长连续递增子序列（连续的递增）if (nums[i + 1] > nums[i]) dp[i + 1] = dp[i] + 1;

• 最长重复子数组（连续，相同的子序列）if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;

• 最长公共子序列（不连续，相同的子序列）
  if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

• 一维dp考虑优化成滑动窗口，二维dp考虑优化成滚动数组（但要考虑遍历顺序，必须从以便利的结果往未遍历的结果递推）

• 推导dp数组时，要从 「分类讨论」 和 「无后效性」 下手，时刻明确dp数组的定义，才能顺利的确定状态转移

参考

Carl：https://mp.weixin.qq.com/s/KJNNOzGxTYhr1ks7tHvk0g