## Monday, August 7, 2017

### [Leetcode] Burst Balloons, Solution

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:
(1) You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
(2) 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100
Example:
Given `[3, 1, 5, 8]`
Return `167`
```    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->    --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167```

[Thoughts]
DP题，很有意思。

DP[i][j] = max( DP[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + DP[k+1][j])      i<k<j

[Code]
``````1:    int maxCoins(vector<int>& nums) {
2:
3:      int n = nums.size();
4:      // add boundary to simplify the corner case
5:      nums.insert(nums.begin(), 1);
6:      nums.push_back(1);
7:
8:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
9:
10:      for(int len = 1; len<=n; len++) {
11:        for(int left = 1; left<=n-len +1; left++) {
12:          int right = left + len -1;
13:          for(int k =left; k<=right; ++k) {
14:            // K is the Balloons destroyed in the last
15:            dp[left][right] = max(
16:              dp[left][right],
17:              nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right],
18:            );
19:          }
20:        }
21:      }
22:      return dp[n];
23:    }
``````
{"ft_lang_label":"__label__en","ft_lang_prob":0.5287811,"math_prob":0.99905556,"size":1522,"snap":"2023-14-2023-23","text_gpt3_token_len":595,"char_repetition_ratio":0.11067194,"word_repetition_ratio":0.0,"special_character_ratio":0.4283837,"punctuation_ratio":0.19148937,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.996538,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-05-29T01:12:13Z\",\"WARC-Record-ID\":\"<urn:uuid:c59152ce-7366-47e6-b89f-0ac5b625929f>\",\"Content-Length\":\"63200\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3de07845-f45d-4736-a72a-be562c093a51>\",\"WARC-Concurrent-To\":\"<urn:uuid:e78041fd-6d9f-4dcd-9152-c7ccd206e969>\",\"WARC-IP-Address\":\"142.250.31.132\",\"WARC-Target-URI\":\"https://fisherlei.blogspot.com/2017/08/leetcode-maximum-length-of-pair-chain.html\",\"WARC-Payload-Digest\":\"sha1:KZPFPSOEO53ORLIUTTJVPYTKX6REETCR\",\"WARC-Block-Digest\":\"sha1:6GPQOWRC264SB3E3VZPGN5C4TE7QKOMT\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224644574.15_warc_CC-MAIN-20230529010218-20230529040218-00248.warc.gz\"}"}