[01背包]leetcode115：不同的子序列(hard)

题目：

---

题解：

思路：01背包

• 本题的实质就是一个01背包模型题，字符串 s 为总物品，字符串 t 为背包体积，问能恰好装满体积 t 的物品方案数。

---

分析出01背包后，状态定义和状态转移方程就好解释了。

• 状态f[i][j]：表示从 s[0...i] 从选能装满体积 t[0...j] 的集合方案数；
• 状态转移：字符串 s 中第 i 个物品选与不选来进行转移。不选 s[i]，那么方案数直接等于 f[i-1][j]，表示从 s[0...i-1] 中选总体积恰好为 t[0...j] 的方案数；选择 s[i]，仅需满足 s[i]==t[j] 的条件，这样方案数需要加上 f[i-1][j-1]，表示除去 t[i] 后，从 s[0...i-1] 中选总体积恰好为 t[0...j-1] 的方案数；

---

代码如下：

class Solution {
public:
    // 01背包模型：s为物品总数，t为背包容量
    int numDistinct(string& s, string& t) {
        return dp2(s,t);
    }
    
    // 优化为一维空间的dp
    int dp2(string& s,string &t)
    {
        int n=s.size(),m=t.size();
        // 头部插空格是为了让下标从1开始递推
        s=" "+s,t=" "+t;
        // 优化掉物品维度
        vector<int> f(m+1,0);
        // 初始化状态：s[0]=' '在t中子序列个数只有1个
        f[0]=1;
        // 进行状态转移，先遍历物品，再遍历背包
        for(int i=1;i<=n;++i)
            for(int j=m;j;j--)// 倒序遍历体积，倒叙来确保f[j-1]是上一层未被更新的状态即f[i-1][j-1]
                if(s[i]==t[j])f[j]=(0LL+f[j]+f[j-1])%INT_MAX;
        return f[m];
    }

    // 二维空间的dp
    int dp1(string& s,string& t)
    {
        int n=s.size(),m=t.size();
        // 头部插空格是为了让下标从1开始递推
        s=" "+s,t=" "+t;
        // f[i][j]表示t[0...j]在s[0...i]中子序列的个数
        vector<vector<int>> f(n+1,vector<int>(m+1,0));
        // 初始化状态：s[0]=' '在t中子序列个数只有1个
        for(int i=0;i<=n;++i)f[i][0]=1;
        // 进行状态转移，先遍历物品，再遍历背包
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                // 不选s[i]，那么s[0...i-1]与t[0...j]匹配
                f[i][j]=f[i-1][j];
                // 选择s[i]，那么s[0...i-1]与t[0...j-1]匹配
                if(s[i]==t[j])f[i][j]=(0LL+f[i-1][j-1]+f[i][j])%INT_MAX;
            }
        return f[n][m];
    }
};