LeetCode刷题实战312:戳气球
共 3219字,需浏览 7分钟
·
2021-07-04 09:02
示例
示例 1:
输入:nums = [3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2:
输入:nums = [1,5]
输出:10
解题
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> dpnums(nums.size() + 2, 1);
//将nums数组进行扩展[1,nums[0], nums[1], ... nums[n], 1]
for(int i=0, j=1; i < nums.size(); i++, j++){
dpnums[j] = nums[i];
}
vector<vector<int>> coins(dpnums.size(), vector<int>(dpnums.size(), 0));//coins[i][j]表示的将下标(i,j)戳破可获得的最大值
int dpNumsSize = dpnums.size();
for(int i = 2; i < dpNumsSize; i++) {
for(int j = 0; j + i < dpNumsSize; j++) {
//上面两层循环用于控制(j,i)的窗口的长度和移动
//下面的循环用于穷举区间(i, j)中最后一个戳破的气球下标,从而确定窗口(i,j)戳破可得的最大值
for(int k = j + 1; k < j + i; k++) {
//coins[j][k] + coins[k][j+i]戳破(i,k)和(k,j)可获得的值
//dpnums[j] * dpnums[k] * dpnums[j+i]戳破k可获得的值
coins[j][j+i] = max(coins[j][j+i], coins[j][k] + coins[k][j+i] + dpnums[j] * dpnums[k] * dpnums[j+i]);
}
}
}
return coins[0][dpNumsSize - 1];
}
};