【leetcode】不同的子序列(01背包)

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

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

示例 1:

输入: S = “rabbbit”, T = “rabbit”
输出: 3
解释:

如下图所示, 有 3 种可以从 S 中得到 “rabbit” 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2:

输入: S = “babgbag”, T = “bag”
输出: 5
解释:

如下图所示, 有 5 种可以从 S 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)

babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

链接：https://leetcode-cn.com/problems/distinct-subsequences

可以判断出这是一道动态规划问题。看样例可以发现，对于S字符串，涉及到的决策问题就是选与不选，而且每个位置只能选一次。我们可以想到经典的01背包问题。
先来分析一下状态和决策。
状态有两个：当前S字符串和当前T字符串。令dp[i][j]表示S字符串前i个元素和T字符串前j个元素配对的个数。这时候有两种情况。

1. 当s[i-1] != s[j-1]时，选不了，dp[i][j] = dp[i-1][j]. 方程的含义就是因为当前状态dp[i][j]的决策是不选择，因此当前状态的i就是上一状态i-1，当前状态的j与上一状态j不变，并且配对个数不变。因此dp[i][j] = dp[i-1][j].
2. 当s[i-1] == s[j-1]时，有两种决策：选与不选。则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. dp[i-1][j-1]的含义是当前状态i就是上一状态i-1，因为做出了选择，所以当前状态j就由上一状态的j-1推过来。

对于初始条件，当 j=0 时，表示T为空串，则对于S配对个数都是1.
这样的时间复杂度和空间复杂度都是O(n^2). 实际上空间复杂度可以用滚动数组优化，像01背包问题一样，dp[i][j]改为dp[j]，然后从右到左递推j.
下面上代码：

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();

        long dp[m+1];
        memset(dp,0,sizeof(dp));
        dp[0] = 1;	//空串，S含空串个数为1
        
        for (int i = 1; i <= n; i++) 
        {
            for (int j = m; j >= 1; j--) //滚动数组
            {
                if(s[i-1] == t[j-1])          
                dp[j] += dp[j-1];
            }
        }
        return dp[m];
    }
};