Introduction

The "pots of gold" game is a classic dynamic-programming problem: two players take turns picking a pot from either end of a row, and both play optimally. The challenge is not just picking the larger visible number, but anticipating the opponent's best reply and planning for the remaining subarray.

Why Greedy Choice Fails

Suppose the pots are [8, 15, 3, 7]. If the first player greedily takes 8, the opponent can respond with 15 and take control of the game. The best opening move is actually 7, because it leads to a better total after considering the opponent's forced choices.

That is why a local rule such as "always take the larger end" does not solve the problem. You need a recurrence that models optimal play on both sides.

Define the Subproblem Carefully

Let dp[i][j] mean the maximum amount of gold the current player can guarantee from the subarray between indices i and j, inclusive.

From position [i, j], the current player has two choices:

• take the left pot arr[i]
• take the right pot arr[j]

But after that move, the opponent also plays optimally and tries to minimize what remains for the current player in the future. That is why the recurrence contains a min inside a max.

The Recurrence

If the current player takes arr[i], the opponent then chooses between the ranges [i + 1, j] and [i, j - 1]. Since the opponent is optimal, the current player should assume the worse of the future outcomes.

The same logic applies if the current player takes arr[j].

The standard recurrence is:

dp[i][j] = max( arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2]) )

Interpretation:

• choose left, then the opponent pushes you into the worse remaining case
• choose right, then the opponent again pushes you into the worse remaining case
• you pick the better of those two guaranteed outcomes

That is the core idea people often miss when first reading the formula.

A Runnable Python Implementation

1def optimal_gold(pots: list[int]) -> int:
2    n = len(pots)
3    dp = [[0] * n for _ in range(n)]
4
5    for i in range(n):
6        dp[i][i] = pots[i]
7
8    for length in range(2, n + 1):
9        for i in range(n - length + 1):
10            j = i + length - 1
11
12            a = dp[i + 2][j] if i + 2 <= j else 0
13            b = dp[i + 1][j - 1] if i + 1 <= j - 1 else 0
14            c = dp[i][j - 2] if i <= j - 2 else 0
15
16            take_left = pots[i] + min(a, b)
17            take_right = pots[j] + min(b, c)
18            dp[i][j] = max(take_left, take_right)
19
20    return dp[0][n - 1]
21
22
23print(optimal_gold([8, 15, 3, 7]))   # 22
24print(optimal_gold([20, 30, 2, 2]))  # 32

For [8, 15, 3, 7], the result is 22, which comes from taking 7 first and then 15 later.

Why the min Is Correct

A common question is: if the current player is maximizing, why is there a min at all?

Because after your move, it becomes the opponent's turn. The opponent is not helping you maximize your final score. They choose the move that leaves you with the smaller of the two future values. So inside each branch of your choice, you assume the opponent will force the worse remaining case.

That is the same minimax idea used in many adversarial game problems.

Complexity and Practical Notes

The DP table has n * n states, and each state is computed in constant time once the smaller intervals are known. So:

• time complexity is O(n^2)
• space complexity is O(n^2)

That is a major improvement over the naive recursive solution, which recomputes the same intervals many times.

If you also need the actual sequence of moves, not just the maximum obtainable sum, you can store a second table recording whether the best choice at [i, j] was left or right.

Common Pitfalls

The biggest mistake is using a greedy strategy based only on the two visible end values. Optimal play depends on future states, not just the immediate reward.

Another mistake is misunderstanding the min term. It is there because the opponent acts adversarially, not randomly.

People also get index handling wrong at the edges of the array. Terms such as dp[i + 2][j] do not always exist, so the implementation must treat out-of-range cases as zero.

Finally, do not confuse "maximum total the first player gets" with "difference between players." Both are valid DP formulations, but they store different meanings and lead to different recurrences.

Summary

• The pots-of-gold problem is a classic minimax dynamic-programming problem.
• Greedy choice fails because the opponent also plays optimally.
• 'dp[i][j] usually stores the best total the current player can guarantee from subarray [i, j].'
• The min inside the recurrence models the opponent forcing the worse future case.
• A bottom-up O(n^2) DP solves the problem efficiently.