Leetcode 115. Distinct Subsequences

[Woodyiiiiiii]

如何推出递归方程？可以举例反证。

class Solution {
    public int numDistinct(String s, String t) {
        
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // init
        for (int i = 0; i <= m; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = 0;
        }
        
        // formula
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) != t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 根据是否匹配
                    // 比如abb和ab，dp[i - 1][j - 1]即选择不匹配，为ab和a；
                    // dp[i - 1][j]则为匹配，可能性有ab和ab
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }
        
        return dp[m][n];
        
    }
}