区间型动态规划题目解析
动态规划适用于有重叠子问题和最优子结构性质的问题。给定一个问题，如果可以将其划分为子问题，并解出其子问题，再根据子问题的解推导/递推以得出原问题的解。LeetCode上关于动态规划的题目众多，除了前述文章的最小路径、股票买卖等问题，区间型动态规划也是一类经典题目。本节将分析LeetCode上两道区间型动态规划题目。
关于动态规划：
- [LeetCode]动态规划及LeetCode题解分析
- 动态规划LeetCode[简单]题全解
- [LeetCode]动态规划之打家劫舍ⅠⅡⅢ
- [LeetCode]动态规划，一举歼灭“股票买卖的最佳时机”问题
- [LeetCode]动态规划，一招团灭最小路径问题
- [LeetCode]动态规划求解博弈问题
1.区间型动态规划特点
区间型动态规划题目的最优解一般表示为dp[i][j]，表示在区间[i, j]上的最优解。通常对某个区间[ i, j ]两端操作，根据dp[i+1][j]或者dp[i][j-1]来递推下一个状态（即递推关系，或者状态转换方程）：
dp[i][j] = temp + max/min(dp[i+1][j], dp[i][j-1])
因为区间是从两端通过i+1或者j-1来不断缩小，所以在遍历的时候不能够像平常的从头到尾遍历，而是以区间的长度len为循环变量，在不同的长度区间里枚举所有可能的状态，并从中选取最优解。
所以，可以从区间类问题里提炼出通俗的解法：
for (int len = 2; len < n; len++){
for (int i = 0; i < n - len; i++){
int j = i + len;
for (int k = i + 1; k < j; k++){
dp[i][j] = temp + max/min(dp[i+1][j], dp[i][j-1]);
}
}
}上述代码的递推关系（状态转移方程）只是一个示例，在具体题目里应根据题目要求做适当变换。
最后返回的，当然应该是在整个区间长度里[ 0, n-1 ]的最优解，即dp[0][n-1].
2.题目分析
375. 猜数字大小 II
解法1：二分法
一碰到这个题目，很容易想到二分法，用两个变量low和high标记区间两端位置，不断取(low+high)/2将每个区间分为两个子区间。本题要求“确保你能赢得这个游戏”，也就是说在最坏情况下也能赢。
所以依据二分法的思想，不断缩小每个区间，枚举每个区间的花费。由于要求最坏情况，所以左右两个区间，应取最大花费。最坏情况下，要尽可能少花费，所以最终要取所有最坏情况下的最小花费值。由此可以写下如下代码：
int getCost(int low, int high){
int res = 0;
int minCost = 65535;
if (low >= high){
return res;
}
for (int i = (low + high) / 2; i <= high; i++){
// 取最大值——最坏情况都能赢，才是确保能够赢
res = i + max(getCost(low, i - 1), getCost(i + 1, high));
minCost = min(minCost, res);
}
return minCost;
}
int getMoneyAmount(int n) {
return getCost(1, n);
}
但是该代码不能通过所有测试用例，会显示超时。
解法2：动态规划
（1）明确数组元素代表的含义
根据前述区间型动态规划的思想，很容易理解dp[i][j]代表在区间[i, j]中最优解。
（2）寻找递推关系
假设 k （i+1 < k < j-1）是 [i...j] 中最后猜的数字，则
dp[i][j] = min {for k = range(i+1, j -1) k + max(dp[i][k-1] , dp[k+1][j])}
（3）数组初始化
区间里只有一个数字时，肯定能够猜对，且无需花费，所以dp[i][i] = 0.
（4）代码
int getMoneyAmount(int n) {
if (n <= 3){
return n - 1;
}
vector<vector<int>>dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++){
dp[i][i] = 0;
}
for (int len = 2; len <= n; len++){
for (int i = 1; i <= n - len + 1; i++){
int minCost = 65535;
int j = i + len - 1;
for (int k = i; k<j; k++){
minCost = min(minCost, k + max(dp[i][k - 1], dp[k + 1][j]));
}
dp[i][j] = minCost;
}
}
return dp[1][n];
}312. 戳气球
（1）明确数组元素代表的含义
dp[i][j] 表示戳破 [i+1...j-1] 号气球的最大收益。
（2）寻找递推关系
假设 k 号气球（i+1 <= k <= j-1）是 [i+1...j-1] 中最后一个被戳破的，则
dp[i][j] = max {for k = range(i+1, j -1) nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]}
（3）代码
int maxCoins(vector<int>& nums) {
// 一前一尾插入1，不影响结果
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>>dp(n, vector<int>(n));
for (int len = 2; len < n; len++){
for (int i = 0; i<n - len; i++){
int j = i + len;
for (int k = i + 1; k<j; k++){
dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][n - 1];
}腾讯云开发者
