Question:
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
Example:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Analysis:
动态规划,dp[i][j]
表示前i
个S
串能组成前j
个T
串的字串个数。
如果S[i] == T[j]
,那么dp[i][j]
就有两种组成字串的可能,一种是由于S[i]
和T[j]
相同,直接用S[i-1]
和T[j-1]
组成的字串在分别加上S[i]
和T[j]
;另一种是直接把S[i]
删掉不考虑。
因此dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
当S[i] != T[j]
,直接把S[i]
删掉不考虑,
因此dp[i][j] = dp[i-1][j]
Answer:
1 |
class (object): |
近期评论