代码随想录第60天 | 647. 回文子串, 516.最长回文子序列, 动态规划总结

647. 回文子串

看完想法：回文串的自定义是左右两边是对称的，单独的一个字母也是回文串（因为左右两边都是空）。dp的迭代过程有一些复杂，可以听一下视频。主要思想是用i, j 表示一段字符串，然后递归遍历这段字符串的头和尾元素相同来判断是不是回文子串。在遍历时，一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

int countSubstrings(string s) {

        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序!
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && ( j - i <=1 || dp[i+1][j-1])) {
                    result++;
                    dp[i][j] = true;

                    }
                }
            }
        
        return result;

516.最长回文子序列

看完想法：与上期题目不同的是，初始化的时候需要把对角线考虑为1，因为迭代时不会遍历到对角线。另一个是当word1和word2相同时，长度+2，不然的话就单独把word1和word2加上去，看哪个可以增加子字符串的长度。

 vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];

时间复杂度：O（n^2）

动态规划总结 

 背包系列问题：

原文地址：https://blog.csdn.net/magnetotell/article/details/140523598

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！