Burst balloons for the most coins

def max_coins(nums):
    v = [1] + nums + [1]                   # padding: missing neighbours count as 1
    n = len(v)
    coins = [[0] * n for _ in range(n)]    # coins[i][j]: best for the balloons strictly between i and j
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            coins[i][j] = max(coins[i][k] + coins[k][j] + v[i] * v[k] * v[j]
                              for k in range(i + 1, j))   # k is burst last
    return coins[0][n - 1]

#include <algorithm>
#include <vector>

int solve(const std::vector<int>& nums) {
    std::vector<int> v{1};
    v.insert(v.end(), nums.begin(), nums.end());
    v.push_back(1);
    const int n = v.size();
    std::vector<std::vector<int>> coins(n, std::vector<int>(n, 0));
    for (int gap = 2; gap < n; ++gap)
        for (int i = 0; i + gap < n; ++i) {
            int j = i + gap;
            for (int k = i + 1; k < j; ++k)              // k is burst last
                coins[i][j] = std::max(coins[i][j], coins[i][k] + coins[k][j] + v[i] * v[k] * v[j]);
        }
    return coins[0][n - 1];
}

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length + 2;
        int[] v = new int[n];
        v[0] = 1; v[n - 1] = 1;
        for (int i = 0; i < nums.length; i++) v[i + 1] = nums[i];
        int[][] coins = new int[n][n];
        for (int gap = 2; gap < n; gap++)
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;
                for (int k = i + 1; k < j; k++)          // k is burst last
                    coins[i][j] = Math.max(coins[i][j], coins[i][k] + coins[k][j] + v[i] * v[k] * v[j]);
            }
        return coins[0][n - 1];
    }
}

function maxCoins(nums) {
  const v = [1, ...nums, 1], n = v.length;
  const coins = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let gap = 2; gap < n; gap++)
    for (let i = 0; i + gap < n; i++) {
      const j = i + gap;
      for (let k = i + 1; k < j; k++)                  // k is burst last
        coins[i][j] = Math.max(coins[i][j], coins[i][k] + coins[k][j] + v[i] * v[k] * v[j]);
    }
  return coins[0][n - 1];
}

fn solve(nums: &[i64]) -> i64 {
    let mut v = vec![1i64];
    v.extend_from_slice(nums);
    v.push(1);
    let n = v.len();
    let mut coins = vec![vec![0i64; n]; n];
    for gap in 2..n {
        for i in 0..n - gap {
            let j = i + gap;
            for k in i + 1..j {                          // k is burst last
                coins[i][j] = coins[i][j].max(coins[i][k] + coins[k][j] + v[i] * v[k] * v[j]);
            }
        }
    }
    coins[0][n - 1]
}

import Data.Array

solve :: [Int] -> Int
solve nums = coins ! (0, n - 1)
  where
    vs = [1] ++ nums ++ [1]
    n = length vs
    v = listArray (0, n - 1) vs
    -- coins ! (i, j): the most for the balloons strictly between i and j; k is the last one burst
    coins = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
    go i j
      | j - i < 2 = 0
      | otherwise = maximum [coins ! (i, k) + coins ! (k, j) + v ! i * v ! k * v ! j | k <- [i + 1 .. j - 1]]