最长回文子串

题源：leetcode

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

动态规划经典题

首先，每一个单独的字母都是回文子串,即dp[i][i] == 1

然后可以考虑转移方程：dp[i][j] == dp[i+1][j-1]&&s[i]==s[j]

下面就是代码：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int length = s.size();
 5         if(length == 0) return "";
 6         if(length == 1) return s;
 7         int start = 0;
 8         int longest = 1;
 9 
10         vector<vector<int>> dp(length,vector<int>(length));
11         for(int i = 0;i<length;i++){
12             dp[i][i] = 1;
13             if(i<length-1){
14                 if(s[i]==s[i+1]){
15                     dp[i][i+1]=1;
16                     start = i;
17                     longest = 2;
18                 }
19             }
20         }
21 
22         for(int l = 3;l<=length;l++){
23             for(int i = 0;i+l-1<length;i++){
24                 int j = i+l-1;
25                 if(dp[i+1][j-1]==1&&s[i]==s[j]) {
26                     dp[i][j]=1;
27                     start = i;
28                     longest = l;
29                 }
30             }
31         }
32 
33         return s.substr(start,longest);
34     }
35 
36 };