LeetCode——不同的子序列

NO.115 不同的子序列困难

思路一：动态规划

dp[i][j]含义：S的前i个字符中出现T的前j个字符序列的个数。

初始化：[S.length+1][T.length+1]包含各自的空串；dp[i][0]=1，即T是空集所以S的任何序列都包含这个子集；dp[0][j]=j!=0?0:1，即S为空集且T为空集则S包含一个T，S为空集而T不为空集则S不包含T。

状态转移：如果S的第i个字符不等于T的第j个字符，dp[i][j]=dp[i-1][j]表示第i个字符不需要参与组成T，例如[3][2]:(abc,ab)=[2][2]:(ab,ab)；

如果相等，dp[i][j]=dp[i-1][j-1]+dp[i-1][j]表示S的第i个字符可以参与(i-1,j-1)组成T也可以不参与(i-1,j)，例如[4][3]:(abcc,abc)=[3][2]:(abc,ab)+[3][3]:(abc,abc)。

public int numDistinct(String s, String t) {
    //初始化
    int[][] dp = new int[s.length() + 1][t.length() + 1];
    for (int i = 0; i < s.length() + 1; i++) {
        dp[i][0] = 1;
    }
    //状态转移
    for (int i = 1; i < s.length() + 1; i++) {
        for (int j = 1; j < t.length() + 1; 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[s.length()][t.length()];
}

时间复杂度：O(m*n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.115 不同的子序列 困难

NO.115 不同的子序列困难