用了一个下午，，，，和晚上，vegetable

思路：

目标的抽取，即问题的解构或者拆解方式：用dp，将问题抽取为在每个母串的各个长度区间上（0-n），各个长度的子串（0-m）在这个区间上匹配的数目。
用一个二维表格，行是字串的各个字母，列是母串的各个字母。每个元素的行i代表此次迭代所用字串为0-i的这一整段（不是一个字母而是将开始到i字母的这一段视为整体）。每个元素的列j代表当前是在迭代从0到j这一整段的母串视为一个整体，元素dp[i][j]表子串0-i对于母串0-j有多少种匹配方式。
！！母串长度x与x+1对于长度为l的子串来说，dp[x+1][l]这个元素存的是从母串0到x+1这一整段对于l长字串的最终（！）结果，他有两个历史数据可以利用：
1.一个是单看行在母串上迭代，子串不变，x+1的母串应该要包含x母串的结果（！），因为0到x+1自然也包含0到x的所有匹配，但这时我统计的是到x+1的，所以除了包含0到x还要有x+1这个多了的这个元素带来的不同，然后两者的加和才是算为x+1的历史数据
2.另一个，x+1这个元素的字符为子串的最后一个字符即匹配时，他的带来的不同应该怎么算呢，子串l-1已经是统计完了的储存在上一行里，l-1在不同的母串区间的结果也是不同的。所以x+1这个元素本身带来的数据应该是（当最后一个字符匹配时）子串l-1在母串长x时（x+1也可以，因为x+1的值绝对等于x，因为x+1这个元素是给这一轮匹配的，上一轮肯定不匹配不影响值）的总的结果数，即已经有的l-1子串在x上的所有匹配方式附加上这个新字符就是我目前x+1这个元素带来的不同，加上之前说的x代表的应包含的结果，总值就是x+1的结果，即l子串在x+1母串的匹配数目，也是dp公式的由来
图片说明 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

这个递归搜索版本在牛客上超时了

class Solution {
public:
    int numDistinct(string S, string T) {
        return recursion(T, 0, S, 0);
    }
    int recursion(string pat, int p, string str, int s){
        int sum=0;
        if(p==pat.size()){
            return 1;
        }
        for(int i=s;i<str.size()-(pat.size()-p)+1;++i){
            if(str[i] == pat[p]){
                sum += recursion(pat, p+1, str, i+1);
            }
        }
        return sum;
    }
};

这个创建了态度空间，其实两个vector应该够了，有时间再改动一个

class Solution {
public:
    int numDistinct(string S, string T) {
        vector<vector<int>> dp;
        vector<int> row;//每一次都要new新的row，因为vector是引用
        for(int i=0;i<S.size()+1;++i)
            row.push_back(1);
        dp.push_back(row);//第一行置1，同时也已经多了第一列，都是方便初始累加数据的由来

        for(int i=0;i<T.size();++i){
            vector<int> row;
            int j=0;
            for(;j<i+1;++j){
                row.push_back(0);
            }//对前面的一些列填0
            for(;j<S.size()+1;++j){
                if(T[i] == S[j-1]){
                    row.push_back(dp[i][j-1]+row[j-1]);
                }else{
                    row.push_back(row[j-1]);
                }
            }//真真计算dp
            dp.push_back(row);
        }
        for(int i=0;i<dp.size();++i) {
            for (int j = 0; j < dp[0].size(); ++j) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return dp[dp.size()-1][dp[0].size()-1];
    }
};
int main() {
    Solution s;
    cout<<s.numDistinct("rabbbit", "rabbit")<<endl;
    cout<<s.numDistinct("", "a")<<endl;
    return 0;
}

输出
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 1 2 3 3 3
0 0 0 0 1 3 3 3
0 0 0 0 0 0 3 3
0 0 0 0 0 0 0 3
3

1
0
0