Burst Balloons

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

func maxCoins(nums []int) int {
    padded := make([]int, 0, len(nums)+2)
    padded = append(padded, 1)
    padded = append(padded, nums...)
    padded = append(padded, 1)
    n := len(padded)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for length := 2; length < n; length++ {
        for l := 0; l+length < n; l++ {
            r := l + length
            for k := l + 1; k < r; k++ {
                cand := dp[l][k] + dp[k][r] + padded[l]*padded[k]*padded[r]
                if cand > dp[l][r] {
                    dp[l][r] = cand
                }
            }
        }
    }
    return dp[0][n-1]
}

from typing import List

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        padded = [1] + nums + [1]
        n = len(padded)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for l in range(n - length):
                r = l + length
                for k in range(l + 1, r):
                    cand = dp[l][k] + dp[k][r] + padded[l] * padded[k] * padded[r]
                    if cand > dp[l][r]:
                        dp[l][r] = cand
        return dp[0][n - 1]

var maxCoins = function(nums) {
    const padded = [1, ...nums, 1];
    const n = padded.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let length = 2; length < n; length++) {
        for (let l = 0; l + length < n; l++) {
            const r = l + length;
            for (let k = l + 1; k < r; k++) {
                const cand = dp[l][k] + dp[k][r] + padded[l] * padded[k] * padded[r];
                if (cand > dp[l][r]) dp[l][r] = cand;
            }
        }
    }
    return dp[0][n - 1];
};

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length + 2;
        int[] padded = new int[n];
        padded[0] = 1;
        padded[n - 1] = 1;
        for (int i = 0; i < nums.length; i++) padded[i + 1] = nums[i];
        int[][] dp = new int[n][n];
        for (int len = 2; len < n; len++) {
            for (int l = 0; l + len < n; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++) {
                    int cand = dp[l][k] + dp[k][r] + padded[l] * padded[k] * padded[r];
                    if (cand > dp[l][r]) dp[l][r] = cand;
                }
            }
        }
        return dp[0][n - 1];
    }
}

function maxCoins(nums: number[]): number {
    const padded: number[] = [1, ...nums, 1];
    const n = padded.length;
    const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let length = 2; length < n; length++) {
        for (let l = 0; l + length < n; l++) {
            const r = l + length;
            for (let k = l + 1; k < r; k++) {
                const cand = dp[l][k] + dp[k][r] + padded[l] * padded[k] * padded[r];
                if (cand > dp[l][r]) dp[l][r] = cand;
            }
        }
    }
    return dp[0][n - 1];
}