雄县网站制作建设中心,网站文章优化技巧,安徽省建设部干部网站,企业网站seo方案案例题目
有 n 个气球#xff0c;编号为0 到 n - 1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球#xff0c;你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和…题目
有 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.length1 n 3000 nums[i] 100 解答
源代码
class Solution {public int[][] res;public int[] val;public int maxCoins(int[] nums) {val new int[nums.length 2];val[0] 1;val[nums.length 1] 1;for (int i 0; i nums.length; i) {val[i 1] nums[i];}res new int[nums.length 2][nums.length 2];for (int i 0; i nums.length 1; i) {Arrays.fill(res[i], -1);}return solve(0, nums.length 1);}// 把戳气球的过程倒过来计算将开区间(left, right)之间填满气球能得到的最多硬币数public int solve(int left, int right) {// 此时(left, right)之间无法添加气球if (left right - 1) {return 0;}if (res[left][right] ! -1) {return res[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);res[left][right] Math.max(res[left][right], sum);}return res[left][right];}
}
总结
每戳一个气球会使本不相邻的两个气球变得相邻所以导致后续难以处理。所以我们换个思路把戳气球的过程倒过来看变成每次插进一个气球插进第一个气球时我们肯定知道它的两边是数字为1的气球超出数组边界然后这个气球的左右两边进行递归也分别当作插进左边和右边的第一个气球。这样以来每次添加气球时气球两边的数字就都能够确定了。
在每次递归时因为当前区间内可以添加气球的位置可能不止一个那么就需要不断对比得到能获得最大硬币数的一个。
