这道题是dp, 我定义的dp[i][j] 为用t[:i] 和s[:j] 的disitinct subsequence排列数
class Solution: # @param {string} s # @param {string} t # @return {integer} def numDistinct(self, s, t): m, n = len(t), len(s) if m == 0 or n == 0: return 0 dp,cur = [0] * n, 1 for i in range(0, m): for j in range(0, n): tmp = dp[j] if t[i] == s[j]: dp[j] = cur else: dp[j] = 0 cur += tmp cur = 0 return sum(dp)
原文：http://www.cnblogs.com/dapanshe/p/4663261.html