不同子序列个数

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：

1. 状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]）
2. 状况2：dp[i][j]=dp[i][j-1] + dp[i-1][j-1]（如果T[i-1]==S[j-1]）
3. 基准条件1:dp[0][j]=1(j>=0)
4. 基准条件2:dp[i][0]=0(i>0)

接下来详细解释以上四个等式：

1. 如果T[i-1] != S[j-1]，那么子序列将不会包含S[j-1]，因此所有的不同子序列会包含在S[0..j-2]中，对应个数为dp[i][j-1]
2. 如果T[i-1] == S[j-1]，那么子序列分两种——包含和不包含s[j-1]
3. 空串在任意字串中只有一种子序列
4. 非空串在任意非空串中都没有对应子序列

举一反三：遇到求子串/子序列个数问题，我们基本上都可以考虑拆解序列，只是拆解方式有所不同，子串问题一般用一维dp数组，子序列问题一般用二维dp数组，根据题目情况的变化，维度或许会增加，但是基本本题的维度还是一维或二维

代码如下：

//
// Created by jt on 2020/8/25.
//
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        // write code here
        int m = T.size(), n = S.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        for (int i = 0; i <= n; ++i) dp[0][i] = 1;
        // for (int i = 1; i <= m; ++i) dp[i][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <=n; ++j) {
                dp[i][j] = T[i-1] == S[j-1] ?  dp[i][j-1] + dp[i-1][j-1] : dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};