leetcode 戳气球
2024-08-30 19:04:45
有 n
个气球,编号为0
到 n-1
,每个气球上都标有一个数字,这些数字存在数组 nums
中。
现在要求你戳破所有的气球。每当你戳破一个气球 i
时,你可以获得 nums[left] * nums[i] * nums[right]
个硬币。 这里的 left
和 right
代表和 i
相邻的两个气球的序号。注意当你戳破了气球 i
后,气球 left
和气球 right
就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
- 你可以假设
nums[-1] = nums[n] = 1
,但注意它们不是真实存在的所以并不能被戳破。 - 0 ≤
n
≤ 500, 0 ≤nums[i]
≤ 100
示例:
输入:[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
思路描述: 区间DP,一个状态不行定义两个状态。正推不行反推,从后往前想,枚举最后一个戳破的气球,定义状态dp[i][j]为i到j的所有气球都戳破的最大价值。dp[i][j] = max(dp[i+1][k]+dp[k+1][j]+ input[i-1] * input[k] * input[j+1]);
k为i到j,注意加的价值为位置k气球的价值,以及i-1和j+1位置气球的价值。
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
if(n==0) return 0;
if(n==1) return nums[0];
int[][] dp = new int[n][n];
dp[0][0] = nums[0] * nums[1];
dp[n - 1][n - 1] = nums[n - 2] * nums[n - 1];
for (int i = 1; i < n - 1; i++) {
dp[i][i] = nums[i - 1] * nums[i] * nums[i + 1];
} for (int t = 1; t < n; t++) {
for (int i = 0; i < n; i++) {
int j = i + t;
if (j < n) {
for (int k = i ; k <= j ; k++) {
int left = k-1 >= i ? dp[i][k-1]:0;
int right = k+1 <= j ? dp[k+1][j]:0;
int p, q, r;
if (i == 0) p = 1;
else p = nums[i - 1];
if (j == n - 1) r = 1;
else r = nums[j + 1];
q = nums[k];
dp[i][j] = Math.max(dp[i][j], left +right + p * q * r);
}
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// System.out.print(dp[i][j] + " ");
// }
// System.out.println();
// }
// System.out.println(dp[0][n - 1]);
return dp[0][n-1];
}
}
最新文章
- iOS开发之开源项目链接
- AppBox升级进行时 - Any与All的用法(Entity Framework)
- 获得ip地理信息的几种方法
- js巧用apply方法实现数组最值以及合并
- jQuery_效果(隐藏和显示)
- Sugarcrm Email Integration
- 在Sql Server 2005中将主子表关系的XML文档转换成主子表“Join”形式的表
- 尽历磨难,搞定OPEN VSWITCH安装
- Python之路:Python 基础(一)
- cocos2dx进阶学习之CCNode
- 基于python的tagcloud
- 闫燕飞:Kafka的高性能揭秘及优化
- 《MySQL必知必会》读书笔记_3
- zTree 3-- jQuery 树插件笔记
- 关于leal和mov
- Rancher之Pipeline JAVA demo
- [转] css选择器中:first-child与:first-of-type的区别
- Linux sort命令使用方法
- WAV与PCM
- io读取文件时考虑问题有?
热门文章
- POJ 1300 最基础的欧拉回路问题
- [luoguP3092] [USACO13NOV]没有找零No Change(状压DP + 二分)
- 【并查集】F.find the most comfortable road
- 洛谷P2814 家谱(gen)
- HDU 4193 Non-negative Partial Sums【单调队列】
- FATE---hdu2159(二重背包)
- T1503 愚蠢的宠物 codevs
- codeforces 873F(后缀数组)
- html5 拖拽元素
- linux字符驱动之poll机制按键驱动