最长回文子串

Leetcode题目：
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

解答思路：
此题使用动态规划思想，首先写出状态转移函数：
我们使用dp[i][j]表示字符串i到j是否是回文子川，如果是则是1，否侧是0.
状态转移函数如下：
dp[i][j] = dp[i+1][j-1] (s[i] =s[j])
dp[i][j]= 0 ([i] !=s[j])
dp[i][i]=1

写出代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
      //判断dp[i][j]是否是回文子串
      if(s.size()<2){
          return s;
      }
      int dp[1000][1000]={0};
      for(int i=0;i
          dp[i][i]=1;
      }
      int start=0;
      int length=1;
      for(int j=0;j
          for(int i=0;i
              if(s[i]!=s[j]){
                  dp[i][j]=0;
              } else if(j-i<=2){
                  dp[i][j]=1;
              } else {
                  dp[i][j]=dp[i+1][j-1];
              }
        //记录最长子串的首位位置和字符串长度  
        if(dp[i][j]==1&&j-i+1>length){
            length = j-i+1;
            start = i;
        }
          }
      }
      return s.substr(start,length);
    }
};

总结：
（1）写出状态转移函数并且明确边界。
（2）思考两个for循环该怎么遍历，i，j谁在前，从大到小还是从小到大遍历，都是可思考的事情。