区间型动态规划入门

状态表示与题目特点

题目会存在Subarray/Substring相关的字眼
用dp[i][j]表示数组/字符串中i，j这一段区间的最优值/可行性/方案总数
大的Subarray/Substring依赖于小的Subarray/Substring
dp[i][j]=max/min/sum/or(dp[i,j之内更小的若干区间])

判断回文子串

O(n^2)的算法中需要检测任意一段字符串是不是回文串

动规四要素
state:dp[i][j]表示i,j这一段是不是回文串
function:dp[i][j] = (dp[i 1][j-1] and s[i]==s[j])
initialization:dp[i][i]=true,dp[i][i 1]==(s[i]==s[i 1])
answer:dp[x][y]对于任意想要检测是否是回文串的下标范围x-y


前面依赖于后面，后面还未算到
解决方法（一）：i倒着循环，j正着循环
解决方案（二）：先循环区间长度，在循环区间起点，再计算终点j=i length-1；

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
   
public:
    string longestPalindrome(string& s) {
   
        if(s.

这篇好文章是转载于：学新通技术网