原题
给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。
子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
样例
给出S = "rabbbit", T =** "rabbit"**
返回 3
解题思路
典型动态规划 - Two Sequence DP
状态cache[i][j]表示 S前i位的不同子序列中有几个和T的前j位相同
初始化
cache[0][0] = 1 T和S都是空串，空串在空串中出现1次
cache[0][j] = 1 T是空串，S只有一种子序列(空串)可以匹配
cache[i][0] = 0 S是空串，T不是空串，S没有子序列可以匹配
状态转移方程
当S[j] != T[i]的时候， cache[i][j] = cache[i][j - 1] //"ABCD"匹配"AC"的方式至少有"ABC"匹配"AC"那么多种
当S[j] == T[i]的时候，还要加上cache[i - 1][j - 1]那么多种匹配方式
如果状态转移方程比较难想，可以先画图找规律
Screenshot at Jun 05 00-07-26.png
完整代码
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
if not s:
return 0
if not t:
return 1
cache = [[0 for j in range(len(s) + 1)] for i in range(len(t) + 1)]
for j in range(len(s) + 1):
cache[0][j] = 1
for i in range(1, len(t) + 1):
for j in range(1, len(s) + 1):
if s[j - 1] == t[i - 1]:
cache[i][j] = cache[i][j - 1] + cache[i - 1][j - 1]
else:
cache[i][j] = cache[i][j - 1]
return cache[len(t)][len(s)]
