312. Burst Balloons

https://leetcode.com/problems/burst-balloons/description/
DP
For each len = ir - il +1,
scan the array with k = il, ... , ir, where k is the last to burst
coin_k = nums[il-1] {nums[il] ... nums[k-1]} nums[k] {nums[k+1] ... nums[ir]} nums[ir+1],
dp[il][ir] = max of coin_k:

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        vector<vector<int>> dp(nums.size(), vector<int> (nums.size(), 0));
        for(int len=1; len<=n; len++) {
            for(int il=1; il <= n-len+1; il++) {
                int ir = il+len-1;
                for(int k=il; k<=ir; k++)
                    dp[il][ir] = max(dp[il][ir], nums[il-1]*nums[k]*nums[ir+1] + dp[il][k-1] + dp[k+1][ir]);
            }
        }
        return dp[1][n];
    }