LeetCode/不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数

1. 递归

题目其实就是要求我们在s中从前往后挑选字符来匹配子序列，得到最后的匹配次数
也就是成功匹配的递归分支

class Solution {
public:
    int numDistinct(string s, string t) {
        return traceback(s,t,0,0);//从初始位置开始递归，从前往后
    }
    int traceback(string &s, string &t,int i,int j){
        if(i>t.size()) return 1;//base case，先判断该条件
        if(j>s.size()) return 0;//base case，s中字符选完
        if(t[i]==s[j]) return traceback(s,t,i+1,j+1)+traceback(s,t,i,j+1);//如果可以匹配，选择匹配和跳过两种分支
        else return traceback(s,t,i,j+1);//不能匹配跳过该字符
    }
};

2. 记忆化搜索

方法一递归的优化，减少重复递归

class Solution {
public:
    int numDistinct(string s, string t) {
        int m =t.size(); int n = s.size();
        vector> memo(m+1,vector(n+1,-1));
        for(int i=0;i> &memo){
        if(memo[i][j]!=-1) return memo[i][j];//跳过该字符
        if(t[i]==s[j])
             memo[i][j] = traceback(s,t,i+1,j+1,memo)+traceback(s,t,i,j+1,memo);
        else memo[i][j] = traceback(s,t,i,j+1,memo);
        return memo[i][j];
    }
};

从前往后

class Solution {
public:
    int numDistinct(string s, string t) {
        vector> memo(t.size(),vector(s.size(),-1));
        return traceback(s,t,0,0,memo);//从前往后
    }
    int traceback(string &s, string &t,int i,int j,vector> &memo){
        if(i>t.size()-1) return 1;//边界条件
        if(j>s.size()-1) return 0;//边界条件
        if(memo[i][j]!=-1) return memo[i][j];//跳过该字符
        if(t[i]==s[j])
             memo[i][j] = traceback(s,t,i+1,j+1,memo)+traceback(s,t,i,j+1,memo);
        else memo[i][j] = traceback(s,t,i,j+1,memo);
        return memo[i][j];
    }
};

从后往前

class Solution {
public:
    int numDistinct(string s, string t) {
        vector> memo(t.size(),vector(s.size(),-1));
        return traceback(s,t,t.size()-1,s.size()-1,memo);
    }
    int traceback(string &s, string &t,int i,int j,vector> &memo){
        if(i<0) return 1;
        if(j<0) return 0;
        if(memo[i][j]!=-1) return memo[i][j];
        if(t[i]==s[j])
             memo[i][j] = traceback(s,t,i-1,j-1,memo)+traceback(s,t,i,j-1,memo);
        else memo[i][j] = traceback(s,t,i,j-1,memo);
        return memo[i][j];
    }
};

3. 动态规划

考虑从前往后递推，与前面带边界递归基本一致
边界条件为dp[0][j]=1，dp[i][0]=0
状态转移方程

class Solution {
public:
    int numDistinct(string s, string t) {
        int m =t.size(); int n = s.size();
        vector> dp(m+1,vector(n+1,0));
        //for(int i=0;i

class Solution {
public:
    int numDistinct(string s, string t) {
        int m =t.size(); int n = s.size();
        vector dp(m+1,0);
        dp[0]=1;
        for(int j=1;j<=n;j++)//从第一列开始
            for(int i=m;i>0;i--)//从下往上遍历，复用前一列上一行的数
                if(t[i-1]==s[j-1])
                    dp[i] = dp[i-1] + dp[i];
    return dp[m];
}
};