AlgoPressAppearance
题目描述
https://leetcode.cn/problems/burst-balloons
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。 求所能获得硬币的最大数量。
示例 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
提示：
- n == nums.length
- 1 <= n <= 300
- 0 <= nums[i] <= 100
思路：模拟【错误】
模拟每次取中间最小的那个数字，这样剩下的数乘积可以最大。 递归算出剩余的数字， 答案有问题 ，测试用例 [9,76,64,21,97,60] 输出 721504 预期结果 1086136
csharp
public class Solution {
public int MaxCoins(int[] nums) {
if(nums.Length == 0){
return 0;
}
if(nums.Length == 1){
return nums[0];
}
else if(nums.Length == 2){
int max = Math.Max(nums[0],nums[1]);
return max + nums[0] * nums[1];
}
else{ //三个数开始必须取中间的数
//找寻 i -> n-2 中最小的数，然后递归计算
int minIndex = 1;
//遍历中间的数字
for(int i=2; i<nums.Length - 1; i++){
if(nums[i] < nums[minIndex]){
minIndex = i;
}
}
//计算本轮数值
int value = nums[minIndex-1] * nums[minIndex] * nums[minIndex+1];
//删除一个数字构造新的数组
int[] newNums = new int[nums.Length - 1];
int index = 0;
for(int i=0; i<nums.Length; i++){
if(i != minIndex){
newNums[index] = nums[i];
index++;
}
}
return value + MaxCoins(newNums);
}
}
}
思路：官方
动态规划，反向处理
参考代码
csharp
public class Solution{
public int MaxCoins(int[] nums){
int n = nums.Length;
int[] temp = new int[n+2]; //创建辅助数组，首尾各设置为1
temp[0] = 1;
temp[n+1] = 1;
for(int i=0; i<n; i++){
temp[i+1] = nums[i]; //复制元素进去
}
//
int[,] dp = new int[n+2,n+2]; //dp[i,j] 表示从i到j能够获最大的分值
//从3区间开始计算，因为两边各加了1，所以其实是从1个数开始就是那
for(int len = 3; len <= n+2; len++){
//i表示开区间的左端点
for(int i=0; i<=n+2-len; i++){
int res = 0;
//k为开区间内的索引
for(int k=i+1; k<i+len-1; k++){
int left = dp[i,k];
int right = dp[k,i+len-1];
res = Math.Max(res,left + temp[i] * temp[k] * temp[i+len-1] + right);
}
dp[i,i+len-1] = res;
}
}
return dp[0,n+1];
}
}
复习：20220712
复习理解反向处理的逻辑：左右为开区间，然后遍历中间，计算sum的最大值
csharp
public class Solution{
public int[,] rec;
public int[] val;
public int MaxCoins(int[] nums){
int n = nums.Length;
val = new int[n+2]; //开区间，左右各为1
for(int i=1; i<=n; i++){
val[i] = nums[i-1]; //将数值都复制进去
}
val[0] = 1;
val[n+1] = 1;
rec = new int[n+2,n+2]; //复制为-1
for(int i=0; i<=n+1; i++){
for(int j=0; j<=n+1; j++){
rec[i,j] = -1;
}
}
//开始依次解题
return Solve(0,n+1);
}
private int Solve(int left, int right){
if(left >= right -1){
return 0;
}
if(rec[left,right] != -1){
return rec[left,right];
}
for(int i=left+1; i<right; i++){
int sum = val[left] * val[i] * val[right];
sum += Solve(left,i) + Solve(i,right);
rec[left,right] = Math.Max(rec[left,right],sum);
}
return rec[left,right];
}
}