Leetcode 115 不同的子序列 C++

思路：一般情况有关字符串子序列或者匹配的问题，都可以用动态规划的方法。

我们通过观察上面的二维数组可以发现，当更新到dp[i][j]时，dp[i][j] >= dp[i][j - 1] 总是成立，再进一步观察发现，当 T[i - 1] == S[j - 1] 时，dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]，若不等， dp[i][j] = dp[i][j - 1]，所以，综合以上，递推式为：

dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)

二维数组dp需要用long，而不能用int型，避免结果超出int型的范围。

class Solution {
public:
    int numDistinct(string s, string t) {
         long dp[t.size() + 1][s.size() + 1];
        for (int i = 0; i <= s.size(); ++i) dp[0][i] = 1;    
        for (int i = 1; i <= t.size(); ++i) dp[i][0] = 0;    
        for (int i = 1; i <= t.size(); ++i) {
            for (int j = 1; j <= s.size(); ++j) {
                dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);
            }
        }
        return dp[t.size()][s.size()]; 
    }
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_43387999/article/details/87991942
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:25:56
阅读 ( 802 )
分类：算法

Leetcode 115 不同的子序列 C++

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看