博文中会简要介绍Leetcode P0115题目分析及解题思路。
“Distinct Subsequences”是一道相对较难但是非常经典的动态规划题目。和它类似的动态规划问题围绕序列和子串做文章，往往和它有着相似的思路。在这篇博文里我会先简单总结类似的这类和序列或者和子串相关的动态规划问题的基本想法与思路，然后再讲解这道题的思路要点。
涉及序列或子串的动态规划问题的一般思路
序列相关的动态规划问题与子串相关的动态规划问题的思路有些许差异。这篇博文里将利用两对比较经典的例子进行对比，来探究序列相关和子串相关的思路差异。这两对例子分别是“最长回文子序列”和“最长回文子串”，“最长公共子序列”和“最长公共子串”。每对例子的前者显然就属于序列相关的问题，而后者则属于子串相关。
“最长回文子序列”和“最长回文子串”
-
序列相关
在“最长回文子序列”中我们可以得到下述思路和递推式
令dp[i][j]是字符串s[i:j]中回文子序列的最大长度， 我们易得， dp[i][i] = 1 dp[i][i+1] = 2, if s[i] = s[i+1] 这一部分很容易理解，单个字符自身是回文的，两个连续字符若相同也是回文的， dp[i][j] = dp[i+1][j-1]+2, if s[i] = s[j] 这一部分也比较容易理解，当s[i]与s[j]相同时，在s[i:j]中的最长回文子序列的长度等于s[i+1:j-1]中的最大长度加上2。但是需要注意的是，在这里我们并没有去判断s[i+1]和s[j-1]是不是相同，换言之我们并没有关心s[i+1:j-1]是不是个回文子序列，我们只关心了它其中的回文子序列的最大长度。 dp[i][j] = max(dp[i+1][j], dp[i][j-1]), otherwise 这一部分表达的是若s[i]和s[j]不相同，则s[i:j]中回文子序列的最大长度取决于s[i+1:j]与s[i:j-1]中的最大值。这里不是s[i+1:j-1]的原因在于，s[i+1]可以和s[j]匹配，反之亦然，这样其最大长度一定是大于等于s[i+1:j-1]中的最大长度的。在这里我们同样也不关心这两个字符串区间是否构成回文子序列。从上述的递推式与思路描述上，我们不难发现，对于序列相关的问题，我们并不关心是否连续合法，换言之，我们并不关心由内向外是不是一个完整的回文子序列，即区间两端是否必须相等。我们关心的是在
s[i:j]中由内而外有多少个相互匹配的字符，并且由它们组成的回文子序列的最大长度是多少。不难看出，这是一种传播，由内向外将值传播，外层的最大值一定大于等于内层的最大值，当到最外层
s[0:len-1]时我们就到了传播的尽头，此时这一层一定是最大值，即我们需要的结果。那么构成这种特性的最重要原因是：子序列不关心连续性，只关心合法性。在这道题里只要两个字符匹配，那么无论其在什么位置，都可以组成一个回文子序列的两端。
-
子串相关
在“最长回文子串”中我们可以得到下述思路和递推式
令dp[i][j]是字符串s[i:j]中以s[i]与s[j]为两端的回文子串的长度， 我们易得， dp[i][i] = 1 dp[i][i+1] = 2, if s[i] = s[i+1] 这一部分很容易理解，单个字符自身是回文的，两个连续字符若相同也是回文的， dp[i][j] = dp[i+1][j-1]+2, if s[i] = s[j] && dp[i+1][j-1] > 0 这一部分也比较容易理解，当s[i]与s[j]相同且s[i+1:j-1]构成回文子串时，s[i:j]这个回文子串的长度等于s[i+1:j-1]的长度加上2。需要注意的是，我们这里强调了，区间内需要连续合法。 dp[i][j] = 0, otherwise 这一部分表达的则是若s[i]和s[j]不相同，则s[i:j]并非回文子串。 最后取每个dp[i][j]的最大值。从上述的递推式与思路描述上，我们不难发现，对于子串相关的问题，我们关心是否连续合法，换言之，我们关心由内向外是不是一个完整的回文子串，即区间两端是否必须相等。
不难看出，我们无法直接求得最大值，因为这个值无法由内而外传播，当
s[i:j]并非回文子串是，这个传播就被中断了。那么构成这种特性的最重要原因是：子串同时关心连续性和合法性。在这道题里只有当两端两个字符匹配且中间区间构成回文子串的时候，我们才能判定连续合法。
“最长公共子序列”和“最长公共子串”
-
序列相关
在“最长公共子序列”中我们可以得到下述思路和递推式
令dp[i][j]是字符串s[0:i-1]与t[0:j-1]中的公共子序列的最大长度 我们易得， dp[0][0] = dp[i][0] = dp[0][i] = 0; 这一部分很容易理解，空串的公共子序列长度为0， dp[i][j] = dp[i-1][j-1]+1, if s[i] = s[j] 这一部分也比较容易理解，当s[i]与s[j]相同时，dp[i][j]等于在s[0:i-2]与t[0:j-2]中的最长公共子序列的长度加上1。 dp[i][j] = max(dp[i-1][j], dp[i][j-1]), otherwise 这一部分表达的是若s[i]和s[j]不相同，则s[0:i-1]与t[0:j-1]之间的最长公共子序列长度取决于dp[i-1][j]和dp[i][j-1]所代表的公共子序列的最大长度中的较大值。从上述的递推式与思路描述上，我们不难发现，在这道与序列相关的问题中，我们同样也不关心是否连续合法，换言之，我们并不关心
s[0:i-1]与t[0:j-1]是否连续匹配，即构成完整的公共子序列。我们关心的是在两个串的前缀区间里有多少个相互匹配的字符，并且由它们组成的公共子序列的最大长度是多少，也就是说我们每次关心的其实仅仅是s[i-1]与t[j-1]是否匹配而已。不难看出，这同样是一种传播，通过不断扩大前缀区间长度将值传播，长区间的最值一定大于等于短区间的最值。
那么构成这种特性的最重要原因是：子序列不关心连续性，只关心合法性。在这道题里只要两个字符匹配，那么其公共子序列长度就会增加。
-
子串相关
在“最长公共子串”中我们可以得到下述思路和递推式
令dp[i][j]是字符串s[0:i-1]以s[i-1]结尾的与t[0:j-1]以t[j-1]结尾的公共子串的长度 我们易得， dp[0][0] = dp[i][0] = dp[0][i] = 0; 这一部分很容易理解，空串的公共子串长度为0， dp[i][j] = dp[i-1][j-1]+1, if s[i] = s[j] 这一部分也比较容易理解，当s[i]与s[j]相同时，dp[i][j]等于在s[0:i-2]中以s[i-2]结尾和t[0:j-2]中以t[j-2]结尾的公共子串的长度加上1。 dp[i][j] = 0, otherwise 这一部分表达的则是若s[i]和s[j]不相同，则在s[0:i-1]中以s[i-1]结尾的和在t[0:j-1]中以t[j-1]结尾的公共子串不存在。 最后取每个dp[i][j]的最大值。从上述的递推式与思路描述上，我们不难发现，在这到子串相关的问题中，我们关心是否连续合法，换言之，若当前
s[i-1]与t[j-1]不相等，则无论前缀区间的公共子串有多长，当前区间内以s[i-1]结尾和以t[j-1]结尾的公共子串都不存在。不难看出，我们无法直接求得最大值，因为这个值无法由短区间传播给长区间，当
s[i-1]与t[j-1]不相等时，这个传播就被中断了。那么构成这种特性的最重要原因是：子串同时关心连续性和合法性。在这道题里只有当
s[i-1]与t[j-1]匹配时才能构成当前区间内以s[i-1]结尾和以t[j-1]结尾的公共子串。
总结
从上述例子的对比，我们不难看出以下几点差异：
-
对于序列相关的动态规划问题，我们只关心合法性；对于子串相关的动态规划问题，我们关心连续性和合法性。
换言之，从思路细节上来说，序列相关的动态规划问题考虑最优子结构时，关注的是以当前考虑对象为结尾的区间的最优解是否包含该对象。
- 如果不包含，就等于前缀区间的最优解；
- 而如果包含（满足合法性），则等于前缀区间最优解累加或组合当前对象会产生的值（比如长度加1）。
而子串相关的动态规划问题则是关注以当前考虑对象为结尾的最优解，即最优解必须包含该对象，此时当前对象成为锚点。
- 如果可以包含，譬如相互匹配，那么满足连续性和合法性，则等于前缀区间的合法值累加或组合当前对象会产生的值；
- 如果不能包含，当前最优解为空，即不连续合法。
-
对于序列相关的动态规划问题，我们可以运用传播的方式直接在传播到最大区间时得到最值解；对于子串相关的动态规划问题，我们需要维护一个变量用于比较和记录每个区间内的最值解。
题解
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
It’s guaranteed the answer fits on a 32-bit signed integer.
回到这道题上，这道题明显是一道序列相关的动态规划问题。根据前面的讲解，我们可以有如下思路和递推表达式：
首先我们明确关注对象，即s[0:i-1]和t[0:j-1]两个区间。然后我们明确比较对象，用于判断合法性，即s[i-1]和t[j-1]。最后我们可以自然地推出最优子结构，
令dp[i][j]表示s[0:i-1]区间内能够构成t[0:j-1]的不同子序列最大总数，
dp[0][0] = 1
dp[i][0] = 1
显然，若t是空串，则s中不同子序列构成空串的只有一个，即开头空串。
dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1])? dp[i-1][j-1]: 0
这个递推表达式表述了合法性判断后的两种情况。第一种是若s[i-1]与t[j-1]不相同，则dp[i][j]的值是dp[i-1][j]传播而来的值，相当于前缀区间内能够构成t[0:j-1]的不同子序列个数；第二种则是若s[i-1]与t[j-1]相同，则dp[i][j]不仅要包括其前缀区间内能够构成t[0:j-1]的不同子序列个数（此时子序列末端不由s[i-1]构成），还要包括前缀区间内能够构成t[0:j-2]的不同子序列个数（这样的子序列的末端加上s[i-1]就可以构成t[0:j-1])，即dp[i-1][j-1]。
以下是Java的题解代码实现。
class Solution {
public int numDistinct(String s, String t) {
int sLen = s.length(), tLen = t.length();
int[][] dp = new int[sLen+1][tLen+1];
dp[0][0] = 1;
for (int idx=1; idx<=sLen; ++idx)
dp[idx][0] = 1;
// DP
for (int i1=1; i1<=sLen; ++i1) {
for (int j2=1; j2<=i1 && j2<=tLen; ++j2) {
dp[i1][j2] = dp[i1-1][j2];
if (s.charAt(i1-1) == t.charAt(j2-1))
dp[i1][j2] += dp[i1-1][j2-1];
}
}
return dp[sLen][tLen];
}
}
以下是C++的题解代码实现。
class Solution {
public:
int numDistinct(string s, string t) {
int s_len = s.length(), t_len = t.length();
vector<vector<long>> dp(s_len+1, vector<long>(t_len+1, 0));
dp[0][0] = 1;
for (int idx=1; idx<=s_len; ++idx)
dp[idx][0] = 1;
// DP
for (int i1=1; i1<=s_len; ++i1) {
for (int j2=1; j2<=i1 && j2<=t_len; ++j2) {
dp[i1][j2] = dp[i1-1][j2];
if (s[i1-1] == t[j2-1])
dp[i1][j2] += dp[i1-1][j2-1];
}
}
return dp[s_len][t_len];
}
};