难得心静。
——2024年6月30日
什么是区间动态规划？
区间动态规划通常以连续区间的求解作为子问题，例如区间 [i, j] 上的最优解用dp[i][j]表示。先在小区间上进行动态规划得到子问题的最优解，再利用小区间的最优解合并产生大区间的最优解。
所以区间动态规划一般需要从小到大枚举所有可能的区间，在枚举时不能向平常的从头到尾遍历，而是以区间长度len为循环变量，在不同的区间长度中枚举所有的可能状态，并从中选取最优解。
区间动态规划区别于一般的动态规划：以区间长度len作为循环变量。
下面以LeetCode5最长回文子串为例：
LeetCode5——最长回文子串
题目描述
给定一个字符串s（s仅由数字和英文大小写字母组成，长度为1~1000），求s中最长的回文子串。例如，s = “babad”，最长的回文子串有“bab”和“aba”，求出任意一个均可。
题解思路
区间动态规划
1. 定义dp数组
定义 dp[i][j ]表示 s[i...j] 是否为回文子串，dp的数值用true和false表示。例如 s = “aba”，那么dp[0][2] = true，dp[0][1] = false；
动态规划的问题，dp的含义都是自己给的，给出含义之后就需要去列关系求解了。
2. 确定dp限制条件
注：len表示字符串长度
①对于任何 len == 1 的字符串，dp[i][j] = 1；
②对于任何 len == 2 的字符串，dp[i][j] = (s[i] == s[j])；（如果s[i] == s[j]， 说明该长度为2的字符串是回文串，比如说“aa”）
③对于任何 len ≥ 3 的字符串， dp[i][j] = (dp[i+1][j-1] && s[i] == s[j])；
解释如下：
第一种情况很好理解，如果字符串长度为1的话，那么他一定是回文子串；
第二种情况也很好理解，如果字符串长度为2，那么只需要判断这两个字符是否相等即可，如果相等则为回文子串，反之则不是；
第三种情况，字符串长度不小于3时，你就需要想到你定义的dp含义和回文字符串的性质了，dp[i][j ]表示 s[i...j] 是否为回文子串，要判断s[i...j]是否为回文子串，那么就必须先知道s[i+1...j-1]是否为回文子串，然后再判断s[i]是否等于s[j]，两者都满足的话那dp[i][j]就等于true了，只要有一个不满足，那么dp[i][j]就为false。
Tips
前两种情况是小区间的最优解，第三种情况就是大区间的最优解。
其实动态规划的问题本质上就是求取了子问题的最优解之后，不断根据子问题的值更新当前dp数组的值，比如非常经典的背包问题。
3. 更新目标字符串长度
不断更新目标字符串长度，只要出现 dp[i][j]=true 的情况就进行更新，并利用substr函数打印即可。（这里如果不理解请看代码部分）
代码实现
再次提醒：区间动态规划的特点是以len为循环变量
区间动态规划伪代码：
for(int len = 1; len <= 序列长度; len++){for(int i = 0; i + len - 1 < 序列长度; i++){int j = i + len - 1;i和j就是区间的端点，i与j相距len个长度。}
}关键代码：
// 获取最长回文子串
string getLongestStr(string s){int n = s.size();string ans = "";// 定义dp数组// dp[i][j]表示从i到j的子字符串是否为回文串vector<vector<bool>> dp(n, vector<bool> (n, false));// len从1开始for(int len = 1; len <= n; len++){for(int i = 0; i + len - 1 < n; i++){int j = i + len - 1;if(len == 1){dp[i][j] = true;}else if(len == 2){dp[i][j] = (s[i] == s[j]);}else{dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);}if(dp[i][j] && ans.size() < len){ans = s.substr(i, len);//更新回文子串}}}return ans;
}结果展示
完整代码
// 区间动态规划
#include<iostream>
#include<vector>
#include<string>using namespace std;// 获取最长回文子串
string getLongestStr(string s){int n = s.size();string ans = "";// 定义dp数组// dp[i][j]表示从i到j的子字符串是否为回文串vector<vector<bool>> dp(n, vector<bool> (n, false));// len从1开始for(int len = 1; len <= n; len++){for(int i = 0; i + len - 1 < n; i++){int j = i + len - 1;if(len == 1){dp[i][j] = true;}else if(len == 2){dp[i][j] = (s[i] == s[j]);}else{dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);}if(dp[i][j] && ans.size() < len){ans = s.substr(i, len);}}}return ans;
}int main(){string s;cout<<"请输入字符串s：";cin>>s;cout<<"最长回文子串为"<<getLongestStr(s)<<endl;return 0;
}看完了是否意犹未尽呢，那再把这个题变一下 ，我现在想求最长回文子序列（或者它的长度）应该怎么做？题目解释：比如我有一个字符串为：s = “aferegga”，那它的最长回文子序列为“aerea”，它的长度为5。
