每一个dp的背后都必然有一个bt。bt的基础上加上记忆化搜索，然后对问题的拆分由从上到下变成从下到上，即可转化为dp。但绝不是所有的bt就天然的可以转化为dp。例如下面这个例子
leetCode 115题，不同的子序列。
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是），下面是示例。
输入: S = “babgbag”, T = “bag”
输出: 5
解释:
如下图所示, 有 5 种可以从 S 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)
最简单的bt解法1，这个我相信不用解释大家都看得懂。
void bt(string& S,int index1,string& T,int index2,int& res){
if(index2 == T.size()) {
res++;
return;
} else {
for(int j = index1; j < S.size() - (T.size() - index2) + 1; j ++) {
if(S[j] != T[index2]) continue;
bt(S, j + 1, T, index2 + 1,res);
}
}
}
int numDistinct(string S, string T) {
int res = 0;
bt(S,0,T,0,res);
return res;
} 能转化成dp的bt解法2，借助dp数组使用了记忆化搜索。（有个小问题，下面这种解法，是不是bt呢？）
int bt(string& S,int len1,string& T,int len2,vector<vector<int>>& dp){
if(dp[len1][len2] != -1) return dp[len1][len2];
if(len2 == 0){
dp[len1][len2] = 1;
return 1;
}
if(len1 == 0) {
dp[len1][len2] = 0;
return 0;
}
dp[len1][len2] = 0;
if(S[len1 - 1] == T[len2 - 1]){
dp[len1][len2] = bt(S,len1 - 1,T,len2 - 1,dp) + bt(S,len1 - 1,T,len2,dp);
}else{
dp[len1][len2] = bt(S,len1 - 1,T,len2,dp);
}
return dp[len1][len2];
}
int numDistinct(string S, string T) {
vector<vector<int>> dp(S.size() + 1,vector<int>(T.size() + 1,-1));
int res = bt(S,S.size() - 1,T,T.size() - 1,dp);
return res;
} 解释如下，动态规划四要素：
状态定义：dp[i][j] 表示 s字符串的前 i 个字符（即从头开始，长为i的串）与 t 字符串的前 j 个字符能产生的子序列数量。
状态转移：对于dp[i][j]
如果 s[i - 1] == t[j - 1] ，那么dp[i][j]是下面这两种情况的加和
使用 s 的第 i 位置字符：dp[i - 1][j - 1]
不使用 s 的第 i 位置字符：dp[i - 1][j]//寄希望于前i - 1个字符能弄出t[j]来
否则 s[i- 1] != t[j - 1]，那么dp[i][j]就只有下面这一种情况
相当于不使用 s 的第 j 位置字符，dp[i - 1][j]
初始化：dp[i][0] = 1，dp[0][j] = 0
结果：dp[s.size()][t.size()]
根据上面的bt解法2，就可以得到下面的dp解法3了
int dp(string& S,string& T,vector<vector<int>>& dp){
for(int i = 0;i < S.size();i++){
dp[i][0] = 1;
}
for(int j = 1; j <= T.size(); j++) {
for(int i = 1; i <= S.length(); i++) {
if(S[j - 1] == T[i-1]) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[S.size()][T.size()];
}
int numDistinct(string S, string T) {
vector<vector<int>> dp(S.size() + 1,vector<int>(T.size() + 1,0));
int res = bt(S,T,dp);
return res;
} 有了解法2，可以很自然的想到解法3。
但是我现在只能自然的想到解法1，想不到解法2，该怎么办呢。解法1怎么样可以演化为解法2呢？
还是说解法2不是由解法1演变而来，而是根据dp表达式得出呢？