贴代码，总觉得这个和LCS十分的神似，特别是递推式，除了打印答案的判断那边要把m[i][j] == m[i + 1][j - 1] + 2换成s[i]==s[j]。考虑"noni"的情况，m[0][3]==m[1][2]+2,然而并不是打印s[0]和s[3]，所以应该限制条件为s[i]==s[j],这样还少打了几下键盘（逃
palindrome_dp.h
1 #pragma once 2 3 #include <string> 4 #include <vector> 5 #include <algorithm> 6 7 using std::string; 8 using std::vector; 9 using std::max; 10 11 void palindrome_ans(const string &s, vector<vector<int> > &m, int i, int j); 12 13 void palindrome_dp(const string &s) 14 { 15 const int n = s.size(); 16 if (n == 0)throw("empty string"); 17 vector<vector<int> > m(n, vector<int>(n, 0)); 18 //边界情况 19 for (int i = 1;i < n;i++) 20 m[i - 1][i] = 0; 21 for (int i = 0;i < n;i++) 22 m[i][i] = 1; 23 24 for(int l=2;l<=n;l++) 25 for (int i = 0;i < n - l + 1;i++) 26 { 27 int j = i + l - 1; 28 if (s[i] == s[j]) 29 m[i][j] = m[i + 1][j - 1] + 2; 30 else 31 m[i][j] = max(m[i + 1][j], m[i][j - 1]); 32 } 33 std::cout << m[2][n - 2] << endl; 34 palindrome_ans(s, m, 0, n - 1); 35 } 36 37 void palindrome_ans(const string &s, vector<vector<int> > &m, int i, int j) 38 { 39 if (i > j)return; 40 if (i == j) 41 { 42 std::cout << s[i]; 43 return; 44 } 45 46 if (s[i] == s[j])//m[i][j] == m[i + 1][j - 1] + 2是不行的，s[i]=s[j]的限制条件更强 47 { 48 std::cout << s[i]; 49 palindrome_ans(s, m, i + 1, j - 1); 50 std::cout << s[j]; 51 } 52 else if (m[i][j] == m[i + 1][j]) 53 palindrome_ans(s, m, i + 1, j); 54 else 55 palindrome_ans(s, m, i, j - 1); 56 }
1 #include "PalindromeDp.h" 2 3 int main(void) { 4 palindrome_dp("character"); 5 palindrome_dp("nowayiton"); 6 return 0; 7 }
