{"id":933,"date":"2017-11-27T08:42:23","date_gmt":"2017-11-27T16:42:23","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=933"},"modified":"2019-08-08T19:14:06","modified_gmt":"2019-08-09T02:14:06","slug":"leetcode-312-burst-balloons","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-312-burst-balloons\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 312. Burst Balloons"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 312. Burst Balloons - \u5237\u9898\u627e\u5de5\u4f5c EP19\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/z3hu2Be92UA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><strong>Problem:<\/strong><\/p>\n\n\n\n<p>Given&nbsp;<code>n<\/code>&nbsp;balloons, indexed from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n-1<\/code>. Each balloon is painted with a number on it represented by array&nbsp;<code>nums<\/code>. You are asked to burst all the balloons. If the you burst balloon&nbsp;<code>i<\/code>&nbsp;you will get&nbsp;<code>nums[left] * nums[i] * nums[right]<\/code>&nbsp;coins. Here&nbsp;<code>left<\/code>&nbsp;and&nbsp;<code>right<\/code>&nbsp;are adjacent indices of&nbsp;<code>i<\/code>. After the burst, the&nbsp;<code>left<\/code>&nbsp;and&nbsp;<code>right<\/code>then becomes adjacent.<\/p>\n\n\n\n<p>Find the maximum coins you can collect by bursting the balloons wisely.<\/p>\n\n\n\n<p><b>Note:<\/b><br>\n(1) You may imagine&nbsp;<code>nums[-1] = nums[n] = 1<\/code>. They are not real therefore you can not burst them.<br>\n(2) 0 \u2264&nbsp;<code>n<\/code>&nbsp;\u2264 500, 0 \u2264&nbsp;<code>nums[i]<\/code>&nbsp;\u2264 100<\/p>\n\n\n\n<p><b>Example:<\/b><\/p>\n\n\n\n<p>Given&nbsp;<code>[3, 1, 5, 8]<\/code><\/p>\n\n\n\n<p>Return&nbsp;<code>167<\/code>\n<\/p>\n\n\n\n<pre class=\"wp-block-preformatted decode:true\">    nums = [3,1,5,8] --&gt; [3,5,8] --&gt;   [3,8]   --&gt;  [8]  --&gt; []\n   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167<\/pre>\n\n\n\n<p><strong>Idea<\/strong><\/p>\n\n\n\n<p>DP<\/p>\n\n\n\n<p><strong>Solution1:<\/strong><\/p>\n\n\n\n<p>C++ \/ Recursion with memoization\n<\/p>\n\n\n\n<pre class=\"wp-block-preformatted lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Runtime: 16 ms\nclass Solution {\npublic:\n    int maxCoins(vector&lt;int&gt;&amp; nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        \n        \/\/ c[i][j] = maxCoins(nums[i:j+1])\n        c_ = vector&lt;vector&lt;int&gt;&gt;(n+2, vector&lt;int&gt;(n+2, 0));\n        \n        return maxCoins(nums, 1, n);\n    }\nprivate:\n    int maxCoins(const vector&lt;int&gt;&amp; nums, const int i, const int j) {\n        if(i&gt;j) return 0;\n        if(c_[i][j]&gt;0) return c_[i][j];\n        \n        if(i==j) return nums[i-1]*nums[i]*nums[i+1];\n        \n        int ans=0;\n        for(int k=i;k&lt;=j;++k)\n             ans=max(ans, maxCoins(nums,i,k-1) + nums[i-1]*nums[k]*nums[j+1] + maxCoins(nums, k+1, j));\n        \n        c_[i][j] = ans;\n        \n        return c_[i][j];\n    }\n    \n    vector&lt;vector&lt;int&gt;&gt; c_;\n};<\/pre>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"Java\">\n\/\/ Author: Huahua\nclass Solution {\n  private int[][] memo;\n  private int[] vals;\n  public int maxCoins(int[] nums) {\n    final int n = nums.length;\n    vals = new int[n + 2];\n    for (int i = 0; i < n; ++i) vals[i + 1] = nums[i];\n    vals[0] = vals[n + 1] = 1;\n    memo = new int[n + 2][n + 2];\n    return maxCoins(1, n);\n  }\n  \n  private int maxCoins(int i, int j) {\n    if (i > j) return 0;\n    if (i == j) return vals[i - 1] * vals[i] * vals[i + 1];\n    if (memo[i][j] > 0) return memo[i][j];\n    int ans = 0;\n    for (int k = i; k <= j; ++k)\n      ans = Math.max(ans, maxCoins(i, k - 1) + vals[i - 1] * vals[k] * vals[j + 1] + maxCoins(k + 1, j));\n    memo[i][j] = ans;\n    return memo[i][j];\n  }\n}\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>Solution2:<\/strong><\/p>\n\n\n\n<p>C++&nbsp; \/ DP\n<\/p>\n\n\n\n<pre class=\"wp-block-preformatted lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Runtime: 9 ms\nclass Solution {\npublic:\n    int maxCoins(vector&lt;int&gt;&amp; nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        \n        \/\/ c[i][j] = maxCoins(nums[i:j+1])\n        vector&lt;vector&lt;int&gt;&gt; c(n+2, vector&lt;int&gt;(n+2, 0));\n        \n        for(int l=1;l&lt;=n;++l)\n            for(int i=1;i&lt;=n-l+1;++i) {\n                int j=i+l-1;\n                for(int k=i;k&lt;=j;++k) {\n                    c[i][j] = max(c[i][j], c[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + c[k+1][j]);\n                }\n            }\n        \n        return c[1][n];\n    }\n};<\/pre>\n\n\n\n<p>Java \/ DP<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\n\/\/ Author: Huahua\nclass Solution {\n  public int maxCoins(int[] nums) {\n    final int n = nums.length;\n    int[] vals = new int[n + 2];\n    for (int i = 0; i < n; ++i) vals[i + 1] = nums[i];\n    vals[0] = vals[n + 1] = 1;\n    int[][] dp = new int[n + 2][n + 2];\n    for (int l = 1; l <= n; ++l)\n      for (int i = 1; i + l <= n + 1; ++i) {\n        int j = i + l - 1;\n        int best = 0;\n        for (int k = i; k <= j; ++k)\n          best = Math.max(best, \n                          dp[i][k - 1] + vals[i - 1] * vals[k] * vals[j + 1] + dp[k + 1][j]);\n        dp[i][j] = best;\n      }\n    return dp[1][n];        \n  }\n}\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><br><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given&nbsp;n&nbsp;balloons, indexed from&nbsp;0&nbsp;to&nbsp;n-1. Each balloon is painted with a number on it represented by array&nbsp;nums. You are asked to burst all the balloons. If&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,165],"tags":[18],"class_list":["post-933","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-hard","tag-dp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/933","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=933"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/933\/revisions"}],"predecessor-version":[{"id":5401,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/933\/revisions\/5401"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=933"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=933"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=933"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}