312. Burst Balloons

问题来自 312. Burst Balloons

---

这道题是动态规划。定义二维数组dp[n][n]，dp[i][j]保存着假设只考虑arr[i,…,j]，我们把它们这些数字delete后能得到的最大值，那么我们的goal就是求dp[0][n-1](下面的代码插入了两个数字，所以是求dp[1][n]).

---

如何求dp[s][e]?我们只要枚举s到e中的所有index：假设这个index的值是最后一步被删掉的，能得到的最大值。我们保存能使得dp[s][e]最大的值。

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