区间类
- 求一段区间的解的max/min/count
- 转移方程通过区间更新
- 从大到小的更新
共性就是最后求[0, n-1] 这样一个区间
逆向思维分析, 从大到小
逆向 ==> 类似分治法
题目
Stone Game
312. Burst Balloons
dp[i][j]表示区间[i...j]中能得到的最大值，那么这个最大值怎么得到呢， 那就轮询一遍这个区间。假设k是该区间中最后一个打破的气球，能获得的最大值，轮询k从i到j，然后取最大值.
int maxCoins(vector<int>& nums) {
vector<int> n(nums);
size_t N = nums.size();
n.emplace(n.begin(), 1);
n.push_back(1);
vector<vector<int>> dp(n.size(), vector<int>(n.size()));
for (size_t len = 1; len <= N; ++len) {
for (size_t start = 1; start <= N - len + 1; ++start) {
size_t end = start + len - 1;
int largest = 0;
for (size_t final = start; final <= end; ++final) {
int coins = dp[start][final-1] + dp[final+1][end];
coins += n[start-1] * n[final] * n[end+1];
largest = max(largest, coins);
}
dp[start][end] = largest;
}
}
return dp[1][N];
}