312. Burst Balloons

Description

Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen becomes adjacent.

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

Note:
(1) You may imaginenums[-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]

Return167

    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

Discussion

Method

Learned from Jiuzhang

DFS + Memorization == 区间型DP

DP[a][b] = the max score get from nums[a] to nums[b].

For each iteration, assume, i in a->b, is the last one get shoot.

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int rst = 0;
        if(nums.size() > 0) {
            nums.insert(nums.begin(),1);
            nums.push_back(1);

            vector<vector<int>> tracker (nums.size(), vector<int>(nums.size(), 0));
            rst = dfs(tracker, nums, 1, nums.size() - 2, 0, nums.size() - 1);
        }
        return rst;
    }

private:
    int dfs(vector<vector<int>> & tracker, vector<int> &nums, int start, int end, int left, int right) {
        int rst = 0;
        if(tracker[start][end] != 0) {
            return tracker[start][end];
        }

        for(int loop = start; loop <= end; ++loop) {
            int cur = nums[loop] * nums[left] * nums[right];
            rst = max(rst, cur + 
                           dfs(tracker, nums, start, loop - 1, left, loop) + 
                           dfs(tracker, nums, loop+1, end, loop, right));
        }


        return tracker[start][end] = rst;
    }
};