赞
踩
有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] *
nums[i] *
nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 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
每戳破一个气球
n
u
m
s
[
i
]
nums[i]
nums[i] ,能获得的硬币数量就是
n
u
m
s
[
i
−
1
]
∗
n
u
m
s
[
i
]
∗
n
u
m
s
[
i
+
1
]
nums[i-1] * nums[i] * nums[i+1]
nums[i−1]∗nums[i]∗nums[i+1]
为了考虑越界,就再开一个数组
a
r
r
[
n
u
m
s
.
l
e
n
g
t
h
+
2
]
arr[nums.length+2]
arr[nums.length+2],来存两个边界 1
我们可以枚举最后一个戳爆的气球
定义dp数组, d p [ i ] [ j ] dp[ i ][ j ] dp[i][j] 表示 戳破 ( i , j ) (i,j) (i,j) 之间的所有气球, 0 < = i < n + 1 0 <= i < n+1 0<=i<n+1
注意如果
i
<
=
j
i <= j
i<=j 中间是没有气球的,因为是开区间所以k的左右两边的区间不会影响k
采用从下至上和从左往右的遍历方式
class Solution { public int maxCoins(int[] nums) { int len = nums.length; // 定义两个边界考虑到越界情况 int[] arr = new int[len+2]; // 越界只能获得1个硬币 arr[0] = arr[len+1] = 1; for(int i = 1; i < len+1; i++) { arr[i] = nums[i-1]; } int[][] dp = new int[len+2][len+2]; // 从下往上枚举 for (int i = len+1; i >= 0; i--) { // 从左往右枚举 (i < j) for(int j = i+1; j < len+2; j++) { // k要在(i,j)范围内 // 枚举最后一个戳爆的气球 for (int k = i + 1; k < j; k++) { dp[i][j] = Math.max(dp[i][j],dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j]); } } } return dp[0][len+1]; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。