1652672550(1).png

思路

看以下题解，思路十分清晰。也很好地解释了递归、记忆化搜索递归以及DP之间的关系。
【PS：虽然我做的时候想到了要点就是，每个字符选择/不选择的判断，并尝试递归，哈哈但我不会写。】
这里的核心递归（dp递推）公式我用一个案例解释：
s：bagg，t：bag

  • 当s[3] ==t[2]时，即末尾的g相等，此时我可以选择
    • 保留末尾g的匹配，然后用剩下的s[0-2] 匹配t[0-1]，s：bagg，t：bag
    • 虽然末尾g相等，但s不care这个相等，用s[0-2] 匹配t[0-2]，s：bagg，t：bag
    • 总的结果是这两种情况相加。

  • 当s[3] !==t[2]时，即末尾的g不相等，此时只能选择

    • 用s[0-2]去匹配完整的t，即t[0-2]，用bag匹配bag，s：bagg，t：bag

      递归（超时）

      1. var numDistinct = function(s, t) {
      2. let sLen =s.length,tLen =t.length
      4. const dfs =function(i,j){
      5.    //从大往小递归，结束在i和j小于0时
      6.    if(j<0){
      7.        //t为空串，空串可以被任意匹配
      8.        return 1
      9.    }
      10.    if(i<0){
      11.        //s为空，无法匹配任何字符串
      12.        return 0
      13.    }
      15.    if(s[i]===t[j]){
      16.        return dfs(i-1,j-1)+dfs(i-1,j)
      17.    }else{
      18.        return dfs(i-1,j)
      19.    }
      20. }
      22. return dfs(sLen-1,tLen-1)
      23. };

      记忆化搜索递归

      var numDistinct = function(s, t) {
let sLen =s.length,tLen =t.length
// 记忆化搜索数组
let memo =new Array(sLen).fill(-1).map(()=>new Array(tLen).fill(-1))
const dfs =function(i,j){
   //从大往小递归，结束在i和j小于0时
   if(j<0){
       //t为空串，空串可以被任意匹配
       return 1
   }
   if(i<0){
       //s为空，无法匹配任何字符串
       return 0
   }

   if(memo[i][j]!==-1) return memo[i][j]
   if(s[i]===t[j]){
       memo[i][j] =dfs(i-1,j-1)+dfs(i-1,j)
       return memo[i][j]
   }else{
       memo[i][j] =dfs(i-1,j)
       return memo[i][j]
   }
}

return dfs(sLen-1,tLen-1)
};

      DP

      注意，还是按照惯例来做吧，免得混乱。
      也就是 dp[i][j] 代表的是dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 ```javascript var numDistinct = function(s, t) { let sLen =s.length,tLen =t.length // dp let dp =new Array(sLen+1).fill().map(()=>new Array(tLen+1).fill(0)) for(let i=0;i<=sLen;i++){ dp[i][0] =1 } for(let i=1;i<=sLen;i++){ for(let j=1;j<=tLen;j++){

         if(s[i-1]===t[j-1]){
       dp[i][j] =dp[i-1][j-1]+dp[i-1][j]
   }else{
       dp[i][j] =dp[i-1][j]
   }

      } }

      return dp[sLen][tLen]

}; ``` 1652672492(1).png