Interval Dynamic Programming | Coin Game - Dynamic Programming / Interval

Problems
1

https://algo.monster/problems/coin_game

2

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.

3

Do you have extra space in the output?

4

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

5

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
  prefixSum.add(0);
  for (int i = 1; i <= n; i++) {
    prefixSum.add(prefixSum.get(i - 1) + coins.get(i - 1));
  }
  return maxScoreV2(coins, prefixSum, 1, n);        
}
6

posted the problem and the fix at https://github.com/realAlgoMonster/contrib/issues/67

7

This reminds me https://leetcode.com/problems/stone-game/

8

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

9

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