你必须掌握动态规划——LeetCode题目5：最长回文子串
你必须掌握动态规划——LeetCode题目5：最长回文子串
原题描述
+
给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。
示例 1
输入："babad"
输出："bab"
注意: "aba" 也是一个有效答案。
示例 2
输入："cbbd"
输出："bb"
原题链接：https://leetcode-cn.com/problems/longest-palindromic-substring
思路解析
+
这道题有多种解法，但我只想谈谈我认为面试中比较重要，并且常考的解题方法——动态规划。
如果不了解动态规划方法的，我在这里简单的介绍下。凡是符合动态规划类型的题目都具有以下两个重要特征，大家务必烂熟于心：
1. 重叠子问题：即原问题和子问题只有规模的不同，原问题可以分解为若干结构规模较小的子问题，可以建立原问题与子问题之间的递推关系。
2. 最优子结构：原问题的最优解一定是在子问题的最优解之上。
可能还是有点虚，那我们一边做题一边了解吧~
假设 表示从 到 的子串是否是回文, 表示字符串 中第 个字符，那么原问题与子问题的关系为：
但是这个递推分解总会到最原子的问题规模。对于这道题来说，最原子的问题是一个字符和两个字符的情况：一个字符本身可以看做回文，两个字符只要相等也是回文，于是有：
好了，看到这里，这道题你已经解决了。你可以直接把上面的递推公式写成递归编写程序，但是动态规划的精髓在于缓存子问题的结果。
动态规划的解题方法是：把上面的 看成是二维矩阵，递推公式表明了矩阵上当前位置的元素和其他位置元素的关系，如此不断递推下去补充矩阵，问题迎刃而解。
那么你可能已经感觉到，动态规划最难的点就是在于寻找递推关系，我们称之为动态方程，而题目中使用的矩阵成为动态规划矩阵。
复杂度分析
+
- 时间复杂度：
- 空间复杂度：
计算步骤
+
1. 在矩阵中填写最原子问题——只有一个字符的情况，记录length为1，并且任意位置都可以作为起始位置。
2. 在矩阵中填写另一个原子问题——只有两个字符的情况，记录最长的length，并记录字符串起始位置。
3. 开始根据递推关系补充矩阵，直到结束，一边填充矩阵一边记录起始位置和最长长度。
C++参考代码
+
class Solution {
public:
string longestPalindrome(string s) {
int length = s.size();
int start = 0, palind_len = 0;
vector<vector<bool>> dp(length, vector<bool>(length, false));
for (int i = 0; i < length; ++i) {
dp[i][i] = true;
start = i;
palind_len = 1;
}
for (int i = 0; i < length - 1; ++i) {
if (s[i] == s[i+1]) {
dp[i][i+1] = true;
start = i;
palind_len = 2;
}
}
for (int stride = 2; stride < length; ++stride) {
for (int i = 0; i + stride < length; ++i) {
if (s[i] == s[i+stride] && dp[i+1][i+stride-1]) {
dp[i][i+stride] = true;
if (palind_len < stride + 1) {
start = i;
palind_len = stride + 1;
}
}
}
}
return s.substr(start, palind_len);
}
};