【LeetCode】动态规划 | 线性DP 序列DP（公共子序列）

博文声明：仅供本人学习交流使用，相关代码和资料已留下引用出处。

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

• 可以不连续

【参考：【你的衣服我扒了 - 《最长公共子序列》】动态规划 - 不相交的线 - 力扣（LeetCode）】

一般这种求解 两个数组或者字符串 求最大或者最小 的题目都可以考虑动态规划，并且通常都定义
dp[i][j] 为 以 A[i], B[j] 结尾的 xxx

718. 最长重复子数组

1143.最长公共子序列

1035. 不相交的线

【参考：516. 最长回文子序列 - 力扣（LeetCode）】

【参考：序列相关 DP 总结 - 知乎】

回文就是从左到右遍历得到的序列与从右到左遍历得到的序列相同的字符串

因此，我们要找到回文子序列，可以通过求原字符串与其反转字符串的最长公共子序列的长度

只不过这个子序列一定是连续的字符串而已

class Solution {
    public int longestPalindromeSubseq(String s) {
        String t=new StringBuilder(s).reverse().toString();
        int m=s.length();
        int n=t.length();

        char[] sc=s.toCharArray();
        char[] tc=t.toCharArray();

        int[][] dp=new int[m+1][n+1];
        // base case
        // dp[i][0]=dp[0][j]=0

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(sc[i-1]==tc[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[m][n];      

    }
}

【参考：115. 不同的子序列 - 力扣（LeetCode）】
【参考：序列相关 DP 总结 - 知乎】

待理解

class Solution {
    public int numDistinct(String s, String t) {
        int m=s.length();
        int n=t.length();
        // m>=n

        char[] sc=s.toCharArray();
        char[] tc=t.toCharArray();

        int[][] dp=new int[m+1][n+1];
        // base case
        // dp[0][j]=0
        for(int i=0;i<=m;i++)
            dp[i][0]=1; // 空串也是子串

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(sc[i-1]==tc[j-1]) // 注意下标
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else
                     dp[i][j]=dp[i-1][j];
            }
        return dp[m][n];      

    }
}