题目：Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of Swhich 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).

字符串S和T，计算从S构成T有多少种不同的方式

思路

dp 算法

dp[i][j]表示构成i长度的t，用到j长度的s，结果等于种类

转移方程：

如果t[i]==s[j],dp[i][j]=dp[i-1][j-1]+dp[i][j-1]

否则：dp[i][j]=dp[i][j-1]

初始值：

dp[0][*]=1表示构成0长度的t，有一种方法

code

func numDistinct(s string, t string) int {
	ls, lt := len(s), len(t)
	dp := make([][]int, lt+1)
	for k := range dp {
		dp[k] = make([]int, ls+1)
	}
	for k := range dp[0] {
		dp[0][k] = 1
	}
	for i := 1; i <= lt; i++ {
		for j := 1; j <= ls; j++ {
			if t[i-1] == s[j-1] {
				dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
			} else {
				dp[i][j] = dp[i][j-1]
			}
		}
	}
	return dp[lt][ls]
}
 

更多内容请移步我的repo：