🌗 115. 不同的子序列

难度: 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int numDistinct(String s, String t) {
        // 思路：
        // dp[i][j] = dp[i - 1][j] -- 当前 s 中的字符不算
        // dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
        int rows = s.length();
        int cols = t.length();
        // 特殊情况特判
        if(rows < cols || rows == 0 || cols == 0) {
            return 0;
        }
        int[][] dp = new int[rows + 1][cols + 1];
        // 初始化
        for(int i = 0; i <= rows; i ++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i <= rows; i ++) {
            for(int j = 1; j <= cols; j ++) {
                int m = i - 1;
                int n = j - 1;
                if(s.charAt(m) == t.charAt(n)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }
        return dp[rows][cols];
    }
}

---

输出