Leetcode 115不同的子序列 动态规划题目

对于一个长度为n的字符串，共有2^n个子序列，如果要暴力搜索。时间复杂度是O(2^n)，很显然，需要动态规划算法

动态规划) O(nm)O(nm)
可以换一种考虑问题的方式：用 SS 中的字符，按顺序匹配 TT 中的字符，问有多少种方式可以匹配完 TT 中的所有字符。

可以用动态规划来做：
f[i][j] 表示用 SS 的前 ii 个字符，能匹配完 TT 的前 jj 个字符的方案数。
初始化：因为 SS 可以从任意一个字符开始匹配，所以 f[i][0]=1,∀i∈[0,len(S)]f[i][0]=1,∀i∈[0,len(S)]。
状态转移：

如果 S[i−1]≠T[j−1]S[i−1]≠T[j−1]，则 S[i−1]S[i−1] 不能匹配 T[j−1]T[j−1]，所以 f[i][j]=f[i−1][j]f[i][j]=f[i−1][j]；
如果 S[i−1]=T[j−1]S[i−1]=T[j−1]，则 S[i−1]S[i−1] 既可以匹配 T[j−1]T[j−1]，也可以不匹配 T[j−1]T[j−1]，所以 f[i][j]=f[i−1][j]+f[i−1][j−1]f[i][j]=f[i−1][j]+f[i−1][j−1]；
时间复杂度分析：假设 SS 的长度是 nn，TT 的长度是 mm，则共有 nmnm 个状态，状态转移的复杂度是 O(1)O(1)，所以总时间复杂度是 O(nm)O(nm)。

字符串问题，常常在前面拼接一个空字符串，这样就可以避免边界问题，这是一个小技巧。