[LeetCode] 312. Burst Balloons

TerryCai 发布于2019-08-16 13:53 / 1868人阅读

Problem

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:

Input: [3,1,5,8]
Output: 167 
Explanation: 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

Solution

class Solution {
    public int maxCoins(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][len];
        return helper(nums, 0, len-1, dp);
    }
    private int helper(int[] nums, int start, int end, int[][] dp) {
        if (start > end) return 0;
        if (dp[start][end] != 0) return dp[start][end];
        int max = 0;
        for (int i = start; i <= end; i++) {
            int curMax = helper(nums, start, i-1, dp) + 
                get(nums, i)*get(nums, start-1)*get(nums, end+1) + 
                helper(nums, i+1, end, dp);
            max = Math.max(max, curMax);
        }
        dp[start][end] = max;
        return max;
    }
    private int get(int[] nums, int i) {
        if (i < 0 || i >= nums.length) return 1;
        return nums[i];
    }
}

idc机房托管私有云 Burst Balloons LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72520.html

leetcode 312. Burst Balloons

摘要：之后该气球将消失，从而其左右两个气球成为相邻的气球。这意味着的时间复杂度。这样就违背了分治法将问题分解为独立问题的要求。此时得到的子队列长度等于，因此将无法拆解，即结束。题目要求 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by arr...

pinecone 2019-08-15 14:49 评论0 收藏0
312. Burst Balloons

摘要：接下来就是方程的问题了。首先肯定是要遍历切分点，然后找使最大的切分点，容易想到这个切分点表示的是扎破气球的位置。还有一种考虑的方式，就是说和不算在内。那么方程现在变成，并且取不到边界或者。 312. Burst Balloons 题目链接：https://leetcode.com/problems... 这题的dp方程还是挺难想的。首先subproblem比较容易：dp[i][j]: ...

calx 2019-08-19 10:45 评论0 收藏0
312. Burst Balloons

public class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] newNum = new int[n+2]; newNum[0] = 1; newNum[n+1] = 1; for(int i=0; i

wyk1184 2019-08-16 10:36 评论0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
力扣(LeetCode)756

摘要：题目地址题目描述给出集合，其所有元素共有种排列。说明给定的范围是。第二种是回溯法求全排列，设置一个全局变量为当前求出的排列数，求出第个全排列，也就是时，停止所有递归否则会超时。题目地址：https://leetcode-cn.com/probl...题目描述：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时,...

Keven 2019-08-16 15:17 评论0 收藏0