115. Distinct Subsequences
一道dp问题，dp的难点在于一是要找准状态，state，二是找递推公式，然后就是初始化，最后就是求结果。就是这几步，一般第一步最难，也就是找到 dp的维度和意义。
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
# dp[i][j] means ending with t[i], s[j] how many subsequence matches
# if t[i] == s[j]: dp[i][j] = sum(dp[i-1][k]) for k in 0...j-1)
# else: dp[i][j] = 0
if not s or not t:
return 0
dp = [[0 for _ in range(len(s))] for _ in range(len(t))]
for i in range(len(s)):
if t[0] == s[i]:
dp[0][i] = 1
for i in range(1, len(t)):
for j in range(len(s)):
if s[j] == t[i]:
dp[i][j] = sum([dp[i-1][k] for k in range(j)])
return sum(dp[-1])
