前言

开篇肯定回顾一下动规5部曲

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

子序列问题经验&技巧：

明确一个常识，子序列&子数组（前者可以不连续，后者要求连续）

下面很多题目都是这两个双子星：

• 最长递增子序列 & 最长递增子数组
• 最长重复数组 & 最长公共子序列
• 回文子串 & 最长回文子序列

另外dp数组的技巧就是

• 如果单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；
• 当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] 其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。（参考）

开撸

1.lc300 最长递增子序列

lc300链接

描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度(注意是子序列)

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4

Solution：
首先dp数组含义：dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度
递推：dp[i] = max(dp[j])+1, 其中 0≤j<i 且 num[j]<num[i]

 public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int res = 1;

        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);   
                }   
                res = Math.max(dp[i],res);
            }
        }
        return res;
    }

当然还有贪心+二分查找的方法，可以减少时间复杂度（这里就不列出了）

2.lc674 最长连续递增序列

lc674链接

描述：

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度

示例：

输入：输入：nums = [1,3,5,4,7] 输出：3

Solution：
连续递增，这样的话就可以只要判断前后大小，一层循环就可以了
dp数组含义：以下标i为结尾的数组的连续递增的子序列长度为dp[i]（起始下标不一定是0）

public int findLengthOfLCIS(int[] nums) {
        int n =nums.length;
        int[] dp = new int[n];

        Arrays.fill(dp,1);

        for(int i=1;i<n;i++)
        {
            if(nums[i]>nums[i-1])
            dp[i]=dp[i-1]+1;
        }
        // 也可以采用上面题目求最大值的方法
        return Arrays.stream(dp).max().getAsInt();

    }

3.lc53 最大子数组和

lc53 链接

描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6

Solution：

 public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];

        int sum=0;
        dp[0] = nums[0];

        int res = nums[0];

        for(int i=1;i<nums.length;i++)
        {
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            res = Math.max(dp[i],res);
        }
        return res;
    }

可以通过滚动数组代替dp数组减少空间复杂度

4.lc718. 最长重复子数组

lc718 链接

描述：

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度

示例：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3

Solution：
两个数组，二维dp

在这里插入代码片

5.lc1143 最长公共子序列

lc1143链接

描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0

示例：

输入：text1 = “abcde”, text2 = “ace” 输出：3

6.lc392 判断子序列

lc392 链接

描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列

示例：

输入：s = “abc”, t = “ahbgdc” 输出：true

Solution：
首先想到的肯定是双指针

 public boolean isSubsequence(String s, String t) {
        int i=0,j=0;

        if(s.length()>t.length()) return false;
        while(i<s.length() && j<t.length())
        {
            if(s.charAt(i)==t.charAt(j))
               i++;
            j++;
        }
       return i==s.length();
    }

动态规划：有点绕，要仔细想

7.lc115 不同的子序列

8.lc1035.不相交的线