力扣_字符串8—不同的子序列-方法

• 动态规划
  • 创建二维 $dp$ 数组， $dp[i][j]$ 表示 $t[0:j-1]$ 在 $s[0:i-1]$ 中出现的次数
  • 状态转移
    • 边界条件：$dp[i][0]=1,dp[0][j]=0$
    • 若 $s[i-1]==t[j-1]$，$s[i-1]$ 可以选择自己是否跟 $t[j-1]$ 匹配
      • $dp[i][j]$ 由两部分组成：
        • 如果匹配，那么 dp[i][j] 其中一部分数量就是 dp[i-1][j-1]
        • 如果选择不匹配（这样可以让前面的字符跟 $t[j-1]$ 匹配)， $dp[i][j]$ 另外一部分就是 $dp[i-1][j]$
    • 若 $s[i-1]!=t[j-1]$，$dp[i][j]=dp[i-1][j]$