1.最优子结构 2.边界 3.状态转移公式
以跳台阶为例，最优子结构为f(10)=f(9) + f(8)，边界是f(1)=1, f(2)=2，状态转移公式f(n)=f(n-1) + f(n-2)
方法三：动态规划
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑“ababa” 这个示例。如果我们已经知道“bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。
C++的动态规划写法：
class Solution { public: string longestPalindrome(string str) { const int n = str.size(); if(n < 2) return str; int s = 0, e = 0; int dp[n] = {0, }; for(int j = 0; j < n; ++j){ for(int i = 0; i < j; ++i){ if(!(dp[i] = dp[i + 1] || str[i] != str[j]) && (e - s) <= (j - i)) s = i, e = j; } } return str.substr(s, e - s + 1); } };
令dp[j][i]从字符串j到i是否为回文串
动态回归方程 dp[j][i]是看j+1和i-1是否为回文串.
class Solution(object): def longestPalindrome(self, s): n = len(s) dp = [[0] * n for _ in range(n)] max_len = float("-inf") res = "" for i in range(n): # dp[i][i] = 1 for j in range(i, -1, -1): if s[i] == s[j] and (i - j < 2 or dp[i - 1][j + 1]): dp[i][j] = 1 if dp[i][j] and i - j + 1 > max_len: max_len = i - j + 1 res = s[j:i + 1] # print(dp) return res
class Solution { public String longestPalindrome(String s) { int n = s.length(); String res = ""; boolean[][] dp = new boolean[n][n]; for(int i = 0 ;i < n; i++){ for(int j = i; j >= 0 ;j --){ if(s.charAt(i) == s.charAt(j) && ( i - j < 2 || dp[i-1][j+1])) dp[i][j] = true; if (dp[i][j] && (i - j + 1 > res.length())){ res = s.substring(j,i+1); } } } return res; } }
原文：https://www.cnblogs.com/samanian/p/11775972.html