动态规划-最长回文子串

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2:输入: "cbbd" 输出: "bb"

  下面看一下代码：

#include<iostream> #include<string> #include<vector> using namespace std;//最长回文子串//动态规划 class Solution { public:string longestPalindrome(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n)); //这是一个二维数组string ans;for (int k = 0; k < n; ++k) { for (int i = 0; i + k < n; ++i) {int j = i + k;cout << "i=" << i << "," << "j=" << j << endl;if (k == 0) {dp[i][j] = 1;}else if (k == 1) {dp[i][j] = (s[i] == s[j]);}else {//i ~ j 为回文子串dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);}if (dp[i][j] && k + 1 > ans.size()) {//substr提取字符串ans = s.substr(i, k + 1);}}cout << "--------------" << endl;}return ans;} };int main(){string str = "babad";Solution s;auto ret = s.longestPalindrome(str);cout << ret << endl;return 0; }

   动态方程的推导和代码地址见：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

程序运行输出：

i=0,j=0          k=0时
i=1,j=1
i=2,j=2
i=3,j=3
i=4,j=4
--------------  k=1时
i=0,j=1
i=1,j=2
i=2,j=3
i=3,j=4
--------------  k=2时
i=0,j=2
i=1,j=3
i=2,j=4
-------------- k=3时
i=0,j=3
i=1,j=4
-------------- k=4时
i=0,j=4
--------------
bab

dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]); 这段代码用利用了 dp[i + 1][j - 1]，这个结果是前面已经计算出来了，当k=4时，字符串最长，最后符合条件的回文子串最长。注意整个循环遍历的过程，用k最为两个下标的间距，然后遍历每种可能的结果判断是否回文，最长的子串最后判断，讲符合条件的子串保存起来。动态规划方程推测极为重要。

 

总结

以上是生活随笔为你收集整理的动态规划-最长回文子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。