代码随想录day55【动态规划】【子序列问题】判断子序列 不同的子序列

判断子序列

力扣题目链接
其实就是最长公共子序列的变种题。
但递推公式可以简化为：
若nums1[i-1] !=nums2[j-1]时
dp[i][j]=dp[i][j-1] //因为s长度更短

var isSubsequence = function(s, t) {
    let dp=new Array(s.length+1).fill(0).map(ele=> new Array(t.length+1).fill(0))

    let res=0
    for(let i=1;i<=s.length;i++){
        for(let j=1;j<=t.length;j++){
            if(s[i-1]===t[j-1]){
                dp[i][j]=dp[i-1][j-1]+1
            }else{
                dp[i][j]=dp[i][j-1]
            }
            res=Math.max(res,dp[i][j])
        }
    }
    return res===s.length
};

不同的子序列

力扣题目链接

1. dp数组含义：
   dp以i-1,j-1结尾的不同子序列的个数
2. 递推公式：
   s[i-1]=t[j-1],dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
   s[i-1] !=t[j-1],dp[i][j]=dp[i-1][j]
3. 初始化：
   dp[0][j]=0,dp[i][0]=1
4. 遍历顺序
   顺序

var numDistinct = function(s, t) {
    let dp=new Array(s.length+1).fill(0).map(()=> new Array(t.length+1).fill(0))
    for(let i=0;i<=s.length;i++){
        dp[i][0]=1
    }
    for(let i=1;i<=s.length;i++){
        for(let j=1;j<=t.length;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[s.length][t.length]
};