vlambda
2020-03-03

区间型动态规划题目解析

动态规划适用于有重叠子问题和最优子结构性质的问题。给定一个问题，如果可以将其划分为子问题，并解出其子问题，再根据子问题的解推导/递推以得出原问题的解。 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];}