[LeetCode] 312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

Solution:
A very good question since that I have to change the way how I do analysis usually. Initially I started with to pick one element (k), then think about how to deal with the rest part. (I think this is may be the common way to think about this question, which will eventually lead to brute force DSF).

But if we change the way to think it a little bit, we will surprise ourselves (at least to me). Instead of picking up element k firstly, how about choose it at the end? Imagine we have elements array from i to j (we can put 1 at each end for boundary conditions). Let's use dp[i][j] represents the max we can get in this range, then dp[i][j] = max{dp[i][j], d[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]}, where i<= k <= j. The key point for understanding this is that we will pick element k as the end.  Amazing, isn't it?

Some details for implementation of dp:
From the transition equation, we can see that dp[i][j] will be calculated from dp[i][k-1] and dp[k+1][j], and k-1 < j and k+1 > i. This indicates that one possible way to do it is to start with larger i and smaller j.  And dp[1][n] is the final answer we need. (for i>j, dp[i][j] is apparently zero due to definition.)

Code:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int>(n+2,0));
        for(int i=n; i>=1; --i){
            for(int j=i; j<=n; ++j){
                for(int k=i; k<=j; ++k){
                    dp[i][j] = max(dp[i][j],  dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);
                }
            }
        }
        return dp[1][n];
    }
};