115.不同的子序列

思路:
动态规划

dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串组成最多个数.

所以动态方程:

当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];

当 S[j] != T[i] , dp[i][j] = dp[i][j-1]

举个例子,如图所示

对于第一行, T 为空,因为空集是所有字符串子集, 所以我们第一行都是 1

对于第一列, S 为空,这样组成 T 个数当然为 0了

至于下面如何进行,大家可以通过动态方程,自行模拟一下!

代码:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n1 = len(s)
        n2 = len(t)
        dp = [[0] * (n1 + 1) for _ in range(n2 + 1)]
        for j in range(n1 + 1):
            dp[0][j] = 1
        for i in range(1, n2 + 1):
            for j in range(1, n1 + 1):
                if t[i - 1] == s[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]  + dp[i][j - 1]
                else:
                    dp[i][j] = dp[i][j - 1]
        #print(dp)
        return dp[-1][-1]

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/10/08/115-不同的子序列/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！