一、题目描述
题目链接:https://leetcode-cn.com/problems/burst-balloons/
二、题目分析
第一眼看到题目的思路还是很直观的,就是dfs列举所有情况,然后使用memo来剪枝,但是还是超时了,以为是压缩状态写得不对,看了题解才知道自己还是太年轻了。
可以说解释得很好了,关键点在于假设当前戳的是最后一个气球(位置k),那么左端(i,k)和右端(k,j)在戳k之前就被戳掉了,因此两者互不影响。
三、代码
public int maxCoins(int[] nums) {
int len = nums.length;
int[][] dp = new int[len+2][len+2];
int[] val = new int[len+2];
val[0] = val[len+1] = 1;
for (int i = 1; i <= len; ++i) {
val[i] = nums[i-1];
}
for (int i = len-1; i >= 0; --i) {
for (int j = i+2; j <= len+1; ++j) {
for (int k = i+1; k < j; ++k) {
int sum = val[i] * val[k] * val[j];
sum += dp[i][k] + dp[k][j];
dp[i][j] = Math.max(dp[i][j],sum);
}
}
}
return dp[0][len+1];
}
本文地址:https://blog.csdn.net/ykben/article/details/107606483
如对本文有疑问, 点击进行留言回复!!
Win10 Build 20180更新了什么 Win10预览版Build 20180更新内容汇总
win10打开程序太多卡顿怎么办 win10秒关程序操作方法
Win10系统Windows Event Log服务可以关闭吗
win10专业版软件不兼容怎么办 Win10专业版兼容性设置方法
Win10 Build 20180更新内容是什么?Win10 Build 20180更新内容发布
网友评论