[数据结构与算法]动态规划（子序列问题）

子序列（不连续）

300. 最长递增子序列

题目连接：https://leetcode.cn/problems/longest-increasing-subsequence/
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。关键点就是这个实例，要弄懂递增子序列的意思。
还有一个点用dp来做的话初始化问题，子序列初始化的时候应该为1,1个元素也是子序列嘛。

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

1143. 最长公共子序列

题目连接：https://leetcode.cn/problems/longest-common-subsequence/
思路：仍然是子序列问题，找两个字符串的公共的子序列，dp数组代表[0…i][0…j]的公共子序列的最大长度，两个字符串从左往右移动如果相同，dp值加一，如果不相同，要么跳过字符串a，要么跳过字符串b。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1=text1.length(),len2=text2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(text1.charAt(i-1)==text2.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[len1][len2];
    }
}

1035. 不相交的线

题目连接：https://leetcode.cn/problems/uncrossed-lines/
最长公共子序列

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1=nums1.length,len2=nums2.length;
        
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(nums1[i-1]==nums2[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[len1][len2];
    }
}

子序列（连续或者说叫子串）

674. 最长连续递增序列

题目连接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
思路：和上一类子序列问题最大的不同就是上一类会和一个元素之前的所有元素比较，而子串你只要和相邻的元素来进行比较。

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

718. 最长重复子数组

题目连接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
思路：仍然是相当于公共串，连续问题。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp=new int[nums1.length+1][nums2.length+1];
        int res=Integer.MIN_VALUE;
        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;
                    res=Math.max(res,dp[i][j]);
                }
            }
        }
        return res==Integer.MIN_VALUE?0:res;
    }
}

53. 最大子数组和

题目连接：https://leetcode.cn/problems/maximum-subarray/

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

编辑距离问题

392. 判断子序列

题目连接：https://leetcode.cn/problems/is-subsequence/
思路：dp数组代表匹配子序列的长度，最后判断dp数组的最后的值和s串长度是否相等来看，如果匹配i，j下标同时移动，如果不匹配那么那个较长的字符串进行移动。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1=s.length(),len2=t.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                    //找到了两个字符串索引都向前推进一个位置
                }else{
                    dp[i][j]=dp[i][j-1];
                    //没找到，父子符串推进
                }
            }
        }
        return dp[len1][len2]==s.length();
    }
}

115. 不同的子序列

题目连接：https://leetcode.cn/problems/distinct-subsequences/
思路：dp数组的含义代表dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
这一类问题，基本是要分析两种情况

s[i - 1] 与 t[j - 1]相等
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

这里可能有同学不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];
初始化问题：dp[i][0]表示什么呢？

dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。

那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1，变成空字符串只有一种方式。

再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。

那么dp[0][j]一定都是0，s如论如何也变成不了t。

class Solution {
    public int numDistinct(String s, String t) {
        int len1=s.length(),len2=t.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

583. 两个字符串的删除操作

题目连接：https://leetcode.cn/problems/delete-operation-for-two-strings/
思路：遍历两个字符串，如何相同的话那么说明不需要进行删除操作，如果不相同的话要么删除a字符串，要么删除b字符串

class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length(),len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[len1][len2];
    }
}

72. 编辑距离

题目连接：https://leetcode.cn/problems/edit-distance/
思路：两个字符串和上一个题类似，索引位置元素相同就无操作，不相同就要进行添加删除替换操作了：
操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是删除元素，添加元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样！
操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

即 dp[i][j] = dp[i - 1][j - 1] + 1;

class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length(),len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(word1.charAt(i-1)!=word2.charAt(j-1)){
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }else{
                    dp[i][j]=dp[i-1][j-1];
                }
                
            }
        }
        return dp[len1][len2];
    }
}

判断回文

647. 回文子串

题目连接：https://leetcode.cn/problems/palindromic-substrings/
思路：判断回文子串数目，建立一个二维数组boolean类型的，dp[][]的含义就是j到i的字符串是否是回文串。
dp的推导过程当两个字符相等时，如果两个字符紧挨着或者两个字符中间只有一个元素或者两个字符的索引相同那么dp[i][j]就为TRUE，这就是相同的索引差值小于等于2的三种情况：索引相同；索引相差为1；索引相差为2，如果字符相同大差值大于2那么说明还要继续收缩判断，dp[i][j]=dp[i-1][j+1];不相同的话dp【i】【j】=false

class Solution {
    public int countSubstrings(String s) {
        int len=s.length();
        //j到i的子串是否是回文串
        boolean[][] dp=new boolean[len][len];
        for(int i=0;i<len;i++){
            for(int j=0;j<=i;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(i-j<=2){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i-1][j+1];
                    }
                }else{
                    dp[i][j]=false;
                }
            }
        }
        int res=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(dp[i][j]){
                    res++;
                }
            }
        }
        return res;
    }
}

516. 最长回文子序列

题目连接：https://leetcode.cn/problems/longest-palindromic-subsequence/
思路：dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
1.如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
2.如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
3.确定遍历顺序
从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，

也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        //dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
        int[][] dp=new int[len][len];
        for(int i=len-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<len;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}