burst ballons

[3, 4, 5, 6] [3, 9, 6] ----> 9 [12, 6] ----> 12 [18] ----> 18

dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + nums[i-1] nums[k] nums[j+1])

当 i == j 还是要走逻辑，不能直接return nums[i];

code

class Solution { public: /**

 * @param nums a list of integer
 * @return an integer, maximum coins
 */  
int maxCoins(vector<int>& nums) {
    // Write your code here
    if(nums.size() == 0)
    {
        return 0;
    }
    vector<int> shadow = {1};
    for(int tmp : nums)
    {
        shadow.push_back(tmp);
    }
    shadow.push_back(1);

    int n = shadow.size();
    vector<vector<int>> dp;
    vector<vector<bool>> flag;

    for(int i = 0; i<n; i++)
    {
        vector<int> tmp(n, 0);
        vector<bool> tmp2(n, false);
        dp.push_back(tmp);
        flag.push_back(tmp2);
    }

    return dfs(dp, flag, shadow, 1, n-2);

}

int dfs(vector<vector<int>>& dp, vector<vector<bool>>& flag, vector<int>& nums, int i, int j)
{
    /*
    if(flag[i][j])
    {
        return dp[i][j];
    }

    int res = 0;
    for(int k = i; k<=j; k++)
    {
        int mid = nums[i-1] * nums[k] * nums[j+1];
        int left = dfs(dp, flag, nums, i, k-1);
        int right = dfs(dp, flag, nums, k+1, j);
        res = max(res, mid+left+right);
    }
    flag[i][j] = true;
    dp[i][j] = res;
    return res;*/

    if(flag[i][j] == true)
    {
        return dp[i][j];
    }

    if(i > j)
    {
        return 0;
    }

    for(int k = i; k <= j; k++)
    {
        int left = dfs(dp, flag, nums, i, k-1);
        int right = dfs(dp, flag, nums, k+1, j);
        int mid = nums[i-1] * nums[k] * nums[j+1];
        dp[i][j] = max(dp[i][j], left + mid + right);
    }

    flag[i][j] = true;
    return dp[i][j];

}

};