Interval Dynamic Programming | Coin Game - Dynamic Programming / Interval

This is broken. My output equals the expected output, and it still says I fail. There is only one correct answer, you should not fail people for providing it.

Do you have extra space in the output?

The “Slight Optimization” solution is incorrect. It gives indexOutOfBound error for all test cases. Please check your answer.

This works

public static int maxScoreV2(List<Integer> coins, List<Integer> prefixSum, int l, int r) {
  if (l == r) {
    return coins.get(r-1);
  int sum = prefixSum.get(r) - prefixSum.get(l-1); 

  int leftPick = maxScoreV2(coins, prefixSum, l + 1, r);
  int rightPick = maxScoreV2(coins, prefixSum, l, r - 1);
  return sum - Math.min(leftPick, rightPick);

public static int coinGameV2(List<Integer> coins) {
  int n = coins.size();
  List<Integer> prefixSum = new ArrayList<>(); // precompute prefix sums
  for (int i = 1; i <= n; i++) {
    prefixSum.add(prefixSum.get(i - 1) + coins.get(i - 1));
  return maxScoreV2(coins, prefixSum, 1, n);        

posted the problem and the fix at

This reminds me

If you use top down approach, I think you would need to increase the recursion depth to not encounter recursion error. sys.setrecursionlimit(n)

managed the top down approach with no prefix sums. I feel like this is much more intuitive than the provided solution

def coin_game(coins: List[int]) -> int:
    dp = [None] * len(coins)
    for i in range(len(coins)):
        dp[i] = [None] * len(coins)
    for i in range(len(coins)):
        dp[i][i] = coins[i]
    def helperFunction(i, j):
        if j < i:
            return 0
        if dp[i][j] is not None:
            return dp[i][j]
        res = max(
            helperFunction(i, i) + min(helperFunction(i+1, j-1), helperFunction(i+2, j)),
            helperFunction(j, j) + min(helperFunction(i+1, j-1), helperFunction(i, j-2))
        dp[i][j] = res
        return res
    ans = helperFunction(0, len(coins)-1)
    return ans