不同的子序列——動态規劃

題目連結

思路：

将兩個字元串從右向左進行周遊；

s[i] 表示s串中從下标 i 開始到末尾的字元串；

t[j]表示t串中從下标 j 開始到末尾的字元串。

例如 “rara” 與 “ra”

首先都是從末尾的a開始周遊，

若此時 i = 0 ，j = 0，代表“rara“與”ra“比對的情況，

且 ‘r’ = ’r’ ，比對，那麼此時有兩種情況：

1. 将“rara”中最前面的 ‘r’ 考慮在内，那麼與“ra“中最前面的‘r’ 相抵消，隻需要考慮”ara“中有多少個”a“即可，則 子序列個數= dp[ i + 1 ][ j + 1]
2. 不将 ”rara“ 中最前面的‘r’考慮在内，那麼則是”rar” 中“ra"的個數， 則子序列個數 = dp[ i + 1][ j ]

将此兩種情況相加，則得到了比對時子序列個數

若不比對，那麼直接等于上述的第二種情況即可。

狀态方程：

當s[i] = t[j]時，dp[i][j] = dp[i+1][j+1] + dp[i+1][j]

當s[i] = t[j]時，dp[i][j] = dp[i+1][j]

注意：

當 j = 字元串長度時，此時 t[ j ] 代表空串，該空串為任意字元串的子序列。

代碼：

public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[i][t.length()] = 1;
        }

        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            for (int j = t.length() - 1; j >= 0; j--) {
                if (c == t.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }

        return dp[0][0];
    }