[LeetCode] 312. Burst Balloons

TerryCai 發布于2019-08-16 13:53 / 1969人閱讀

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];
    }
}

GPU云服務器云服務器 Burst Balloons LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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