312. Burst balloons

312_solution1_tab.c

#include <stdlib.h>

int maxCoins(int *nums, int numsSize) {
  int N = numsSize + 2;
  int *a = malloc(N * sizeof(int)); // pad: [1, nums..., 1]
  a[0] = a[N - 1] = 1;
  for (int i = 0; i < numsSize; i++)
    a[i + 1] = nums[i];

  int *dp = calloc(N * N, sizeof(int)); // dp[l * N + r]; len < 2 → 0 already

  for (int len = 2; len < N; len++) { // distance between walls
    for (int l = 0; l + len < N; l++) {
      int r = l + len;
      for (int k = l + 1; k < r; k++) {
        int coins = dp[l * N + k] + dp[k * N + r] + a[l] * a[k] * a[r];
        if (coins > dp[l * N + r])
          dp[l * N + r] = coins;
      }
    }
  }
  int res = dp[N - 1];
  free(a);
  free(dp);
  return res;
}

312_solution2_memo.c

#include <stdlib.h>

static int *a, *dp, N; // dp[l * N + r], -1 = not computed

static int f(int l, int r) {
  if (r - l < 2)
    return 0; // nothing strictly between l and r
  if (dp[l * N + r] != -1)
    return dp[l * N + r];

  int best = 0;
  for (int k = l + 1; k < r; k++) { // k = last balloon burst in (l, r)
    int coins = a[l] * a[k] * a[r] + f(l, k) + f(k, r);
    if (coins > best)
      best = coins;
  }
  return dp[l * N + r] = best;
}

int maxCoins(int *nums, int numsSize) {
  N = numsSize + 2;
  a = malloc(N * sizeof(int)); // pad: [1, nums..., 1]
  a[0] = a[N - 1] = 1;
  for (int i = 0; i < numsSize; i++)
    a[i + 1] = nums[i];

  dp = malloc(N * N * sizeof(int));
  for (int k = 0; k < N * N; k++)
    dp[k] = -1;
  int res = f(0, N - 1);
  free(a);
  free(dp);
  return res;
}

312_solution1_tab.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int maxCoins(vector<int> &nums) {
    vector<int> a = {1};
    a.insert(a.end(), nums.begin(), nums.end());
    a.push_back(1);

    int N = a.size();
    vector<vector<int>> dp(N, vector<int>(N, 0)); // len < 2 → 0 already

    for (int len = 2; len < N; len++) { // distance between walls
      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] + a[l] * a[k] * a[r]);
        }
      }
    }
    return dp[0][N - 1];
  }
};

312_solution2_memo.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int f(int l, int r, vector<int> &a, vector<vector<int>> &dp) {
    if (r - l < 2)
      return 0; // nothing strictly between l and r
    if (dp[l][r] != -1)
      return dp[l][r];

    int best = 0;
    for (int k = l + 1; k < r; k++) { // k = last balloon burst in (l, r)
      int coins = a[l] * a[k] * a[r] + f(l, k, a, dp) + f(k, r, a, dp);
      best = max(best, coins);
    }
    return dp[l][r] = best;
  }

  int maxCoins(vector<int> &nums) {
    vector<int> a = {1};
    a.insert(a.end(), nums.begin(), nums.end());
    a.push_back(1); // pad: [1, nums..., 1]

    int N = a.size();
    vector<vector<int>> dp(N, vector<int>(N, -1));
    return f(0, N - 1, a, dp);
  }
};

312_solution1_tab.go

package dp

func maxCoins(nums []int) int {
    a := append(append([]int{1}, nums...), 1) // pad: [1, nums..., 1]

    N := len(a)
    dp := make([][]int, N) // len < 2 → 0 already
    for i := range dp {
        dp[i] = make([]int, N)
    }

    for length := 2; length < N; length++ { // distance between walls
        for l := 0; l+length < N; l++ {
            r := l + length
            for k := l + 1; k < r; k++ {
                dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])
            }
        }
    }
    return dp[0][N-1]
}

312_solution2_memo.go

package dp

func maxCoins(nums []int) int {
    a := append(append([]int{1}, nums...), 1) // pad: [1, nums..., 1]

    N := len(a)
    dp := make([][]int, N) // -1 = not computed
    for i := range dp {
        dp[i] = make([]int, N)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var f func(l, r int) int
    f = func(l, r int) int {
        if r-l < 2 {
            return 0 // nothing strictly between l and r
        }
        if dp[l][r] != -1 {
            return dp[l][r]
        }

        best := 0
        for k := l + 1; k < r; k++ { // k = last balloon burst in (l, r)
            coins := a[l]*a[k]*a[r] + f(l, k) + f(k, r)
            best = max(best, coins)
        }
        dp[l][r] = best
        return best
    }

    return f(0, N-1)
}

312_solution1_tab.java

class Solution {
    public int maxCoins(int[] nums) {
        int N = nums.length + 2;
        int[] a = new int[N]; // pad: [1, nums..., 1]
        a[0] = a[N - 1] = 1;
        System.arraycopy(nums, 0, a, 1, nums.length);

        int[][] dp = new int[N][N]; // len < 2 → 0 already

        for (int len = 2; len < N; len++) { // distance between walls
            for (int l = 0; l + len < N; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++) {
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
                }
            }
        }
        return dp[0][N - 1];
    }
}

312_solution2_memo.java

import java.util.Arrays;

class Solution {
    private int f(int l, int r, int[] a, int[][] dp) {
        if (r - l < 2)
            return 0; // nothing strictly between l and r
        if (dp[l][r] != -1)
            return dp[l][r];

        int best = 0;
        for (int k = l + 1; k < r; k++) { // k = last balloon burst in (l, r)
            int coins = a[l] * a[k] * a[r] + f(l, k, a, dp) + f(k, r, a, dp);
            best = Math.max(best, coins);
        }
        return dp[l][r] = best;
    }

    public int maxCoins(int[] nums) {
        int N = nums.length + 2;
        int[] a = new int[N]; // pad: [1, nums..., 1]
        a[0] = a[N - 1] = 1;
        System.arraycopy(nums, 0, a, 1, nums.length);

        int[][] dp = new int[N][N];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return f(0, N - 1, a, dp);
    }
}

312_solution1_tab.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  const a = [1, ...nums, 1]; // pad: [1, nums..., 1]

  const N = a.length;
  const dp = Array.from({ length: N }, () => new Array(N).fill(0)); // len < 2 → 0 already

  for (let len = 2; len < N; len++) {
    // distance between walls
    for (let l = 0; l + len < N; l++) {
      const r = l + len;
      for (let k = l + 1; k < r; k++) {
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
      }
    }
  }
  return dp[0][N - 1];
};

312_solution2_memo.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  const a = [1, ...nums, 1]; // pad: [1, nums..., 1]

  const N = a.length;
  const dp = Array.from({ length: N }, () => new Array(N).fill(-1));

  const f = (l, r) => {
    if (r - l < 2) return 0; // nothing strictly between l and r
    if (dp[l][r] !== -1) return dp[l][r];

    let best = 0;
    for (let k = l + 1; k < r; k++) {
      // k = last balloon burst in (l, r)
      const coins = a[l] * a[k] * a[r] + f(l, k) + f(k, r);
      best = Math.max(best, coins);
    }
    return (dp[l][r] = best);
  };

  return f(0, N - 1);
};

312_solution1_tab.py

from typing import List


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        a = [1] + nums + [1]  # pad: [1, nums..., 1]

        N = len(a)
        dp = [[0] * N for _ in range(N)]  # len < 2 → 0 already

        for length in range(2, N):  # distance between walls
            for l in range(N - length):
                r = l + length
                for k in range(l + 1, r):
                    dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r])
        return dp[0][N - 1]

312_solution2_memo.py

from typing import List


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        a = [1] + nums + [1]  # pad: [1, nums..., 1]

        N = len(a)
        dp = [[-1] * N for _ in range(N)]

        def f(l: int, r: int) -> int:
            if r - l < 2:
                return 0  # nothing strictly between l and r
            if dp[l][r] != -1:
                return dp[l][r]

            best = 0
            for k in range(l + 1, r):  # k = last balloon burst in (l, r)
                coins = a[l] * a[k] * a[r] + f(l, k) + f(k, r)
                best = max(best, coins)
            dp[l][r] = best
            return best

        return f(0, N - 1)

312_solution1_tab.rs

impl Solution {
    pub fn max_coins(nums: Vec<i32>) -> i32 {
        let mut a = vec![1]; // pad: [1, nums..., 1]
        a.extend(&nums);
        a.push(1);

        let n = a.len();
        let mut dp = vec![vec![0; n]; n]; // len < 2 → 0 already

        for len in 2..n {
            // distance between walls
            for l in 0..n - len {
                let r = l + len;
                for k in l + 1..r {
                    dp[l][r] = dp[l][r].max(dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
                }
            }
        }
        dp[0][n - 1]
    }
}

312_solution2_memo.rs

impl Solution {
    pub fn max_coins(nums: Vec<i32>) -> i32 {
        let mut a = vec![1]; // pad: [1, nums..., 1]
        a.extend(&nums);
        a.push(1);

        let n = a.len();
        let mut dp = vec![vec![-1; n]; n];
        Self::f(0, n - 1, &a, &mut dp)
    }

    fn f(l: usize, r: usize, a: &[i32], dp: &mut Vec<Vec<i32>>) -> i32 {
        if r - l < 2 {
            return 0; // nothing strictly between l and r
        }
        if dp[l][r] != -1 {
            return dp[l][r];
        }

        let mut best = 0;
        for k in l + 1..r {
            // k = last balloon burst in (l, r)
            let coins = a[l] * a[k] * a[r] + Self::f(l, k, a, dp) + Self::f(k, r, a, dp);
            best = best.max(coins);
        }
        dp[l][r] = best;
        best
    }
}