Games with DP and memoisation

Why this matters when you build with AI

Ask an AI tool for a solver of a two-player game with scores, and it often writes a plain recursive search. That search has two common faults. It has no memo, so it repeats the same work and slows down fast as the input grows. Or it adds the opponent's score where it should subtract it, so the program reports a result for the wrong player. The output looks like a normal number, and nothing in the code shows the fault.

Two checks catch both faults. The first is a brute force on inputs small enough to finish, compared with the fast solver on many random inputs. The second is a hand computation on a three-item input, where you can see each step. This lesson builds both kinds of check and uses them on every program.

Some terms first. A state is everything that decides how the rest of the game goes. A memo is a table that stores the answer for a state the first time it is computed, so the same state is never solved twice. A bitmask is an integer whose bits mark which items are in a set. Bit i is 1 when item i is in the set. A score-difference value is the best lead one player can get over the other from a state, with both players playing well.

The idea: the state decides the future

In the earlier lessons of this module, the state was a pile count. Here the state is often bigger. Two kinds show up most.

• A range state. The remaining items form a contiguous block, say crates l to r. There are about n squared states for n items.
• A set state. The remaining items are any subset. Bitmask states have 2^n values, so they fit only for n up to about 20.

A memoised search keeps the recursion of the game tree, and adds a table of answers. The first call to a state does the work. Later calls return the stored answer. The number of distinct states sets the running time, not the number of paths through the game tree. That number is often much smaller, and the difference is the whole point of the technique.

Scores: work with the difference

Suppose two players take items, and each wants the largest total for themselves. The sum of all items is fixed, so a larger total for me is the same as a larger lead over the opponent. Let total be the sum of all items, mine my total and theirs the opponent's total. Then mine - theirs = 2 * mine - total. Maximising mine and maximising the lead give the same optimal play.

The lead is easier to work with, because it has one recurrence for both players. Define f(s) as the best lead the player to move can get from state s, counting only what is still to be taken. If a move m takes gain(m) and leaves state s', then the opponent moves next in s'. The opponent's best lead from s' is f(s'). So the move's value for the mover is gain(m) - f(s'). The mover picks the best move:

f(s) = max over legal moves m of ( gain(m) - f(s after m) )
f(empty) = 0

The minus sign is the whole idea. Each time the turn passes, the lead flips to the other player. The sign error in the common mistakes section comes from forgetting this flip.

A worked example by hand

Use the crate line game. Crates stand in a row with values a[1..n]. On a turn, the mover takes one of three things: the leftmost crate, the two leftmost crates, or the rightmost crate. The mover gets the sum of what they took. The game ends when no crate is left.

Take the row 3 9 1. Write [9,1] for the state with crates 9 and 1 left, and so on. Compute the values from the smallest states up.

• f([1]) = 1, since the only move takes 1.
• f([9]) = 9.
• f([3]) = 3.
• f([9,1]): take 9 leaves [1], value 9 - 1 = 8. Take 9 and 1 together gives 10, leaving nothing. Take 1 leaves [9], value 1 - 9 = -8. The best is 10.
• f([3,9]): take 3 leaves [9], value 3 - 9 = -6. Take 3 and 9 gives 12. Take 9 leaves [3], value 9 - 3 = 6. The best is 12.
• f([3,9,1]): take 3 leaves [9,1], value 3 - 10 = -7. Take 3 and 9 leaves [1], value 12 - 1 = 11. Take 1 leaves [3,9], value 1 - 12 = -11. The best is 11.

So the first player leads by 11. The total is 13, so the first player gets (13 + 11) / 2 = 12 and the second player gets 1. The line of play is: the first player takes 3 and 9, and the second player takes the last crate, 1.

Notice the step for [3,9,1] that took 3 alone. Its value is 3 - 10 = -7. The 10 is the lead the opponent gets from [9,1]. The opponent's lead is subtracted, because the opponent moves next. This is the minus sign of the recurrence at work.

Standard technique: top-down memoised search in C++17

This version follows the recurrence directly. It stores the answer for each range [l, r) in a table of size (n+1) x (n+1). The sentinel NOT_SET marks an entry that has not been computed. Ranges are half-open, so [l, r) holds crates a[l] up to a[r-1].

#include <bits/stdc++.h>
using namespace std;
 
// Top-down memoised search over the crate line. A state is the range [l, r) of crates left.
// memo[l][r] holds the mover's best difference, or NOT_SET if it has not been computed.
const long long NOT_SET = LLONG_MIN;
 
vector<long long> a;
vector<vector<long long>> memo;
 
long long best_diff(int l, int r) {
    if (l >= r) return 0;  // no crates left, so no more gain
    long long &slot = memo[l][r];
    if (slot != NOT_SET) return slot;
    long long res = a[l] - best_diff(l + 1, r);
    if (l + 1 < r) res = max(res, a[l] + a[l + 1] - best_diff(l + 2, r));
    res = max(res, a[r - 1] - best_diff(l, r - 1));
    return slot = res;
}
 
int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (auto &x : a) cin >> x;
    memo.assign(n + 1, vector<long long>(n + 1, NOT_SET));
    cout << best_diff(0, n) << "\n";
    return 0;
}

The reference is a plain recursion with no memo, built on lists, and it was run as a separate program. On 400 random inputs with n from 1 to 11 and values from 0 to 20, this program agreed with the reference on every case. Output on the input 3 9 1 is 11, the same as the hand computation.

The base case matters most: best_diff(l, r) returns 0 when l >= r. The mistakes section shows what goes wrong when it is changed.

Worked problem: Crate line

Two players share a row of n crates. On a turn the mover takes one of three moves: the leftmost crate, the two leftmost crates, or the rightmost crate. The mover scores the sum of what they take. Both players play to maximise their own score. The game ends when no crates are left.

Input:

• Line 1: n, with 1 at most n at most 2000.
• Line 2: n integers a_1 ... a_n, each from 0 to 10^6.

Output:

• Line 1: diff D, where D is the best lead of the first player under optimal play.
• Line 2: mover M other O, where M is the first player's total and O is the second player's total.

The sample input and output are shown below.

3
3 9 1

diff 11
mover 12 other 1

The solution

This program fills the same table bottom-up, by increasing length of the remaining row. It needs no recursion, so the depth of the call stack is never an issue.

#include <bits/stdc++.h>
using namespace std;
 
// Crate line game. Crates a[1..n] stand in a row. A turn takes either
//   (a) the leftmost crate, or
//   (b) the two leftmost crates, or
//   (c) the rightmost crate.
// The mover gets the sum of what they take. Both players want the larger total for themselves.
// Output: the best difference (mover total minus other total) under optimal play, then the mover's total.
int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 2, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    // d[l][r] = best difference for the mover when crates l..r remain. d = 0 when l > r (no crates).
    vector<vector<long long>> d(n + 3, vector<long long>(n + 3, 0));
    auto sum = [&](int l, int r) {
        long long s = 0;
        for (int i = l; i <= r; ++i) s += a[i];
        return s;
    };
    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            long long best = LLONG_MIN;
            // (a) take one from the left
            best = max(best, a[l] - d[l + 1][r]);
            // (b) take two from the left, if there are two
            if (l + 1 <= r) best = max(best, sum(l, l + 1) - d[l + 2][r]);
            // (c) take one from the right
            best = max(best, a[r] - d[l][r - 1]);
            d[l][r] = best;
        }
    }
    long long total = sum(1, n);
    long long diff = n ? d[1][n] : 0;
    long long mover = (total + diff) / 2;
    cout << "diff " << diff << "\n";
    cout << "mover " << mover << " other " << total - mover << "\n";
    return 0;
}

Real output of this program on the sample, compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0 (no warnings):

diff 11
mover 12 other 1

A second sample, 5 then 4 1 7 2 9, gives diff 9 and mover 16 other 7.

How it was tested

A brute force that recurses on the list of remaining crates, with no table and no memo, is the reference. The two programs were compared on 700 random inputs with n from 1 to 11 and values from 0 to 20. There were 0 mismatches. A third program, the top-down version above, agreed with the reference on 400 more random cases.

The solution was also run on a random input with n = 2000 and values up to 10^6. It finished in 0.09 seconds and used 35 MB of memory, as measured by /usr/bin/time -v. The brute force on the same family took 57 seconds at n = 24, which is why it is only a reference for small inputs.

Complexity

The table has about n^2 / 2 useful entries, and each entry costs constant work, so the time is O(n^2). The table stores 8-byte integers in an (n+3) x (n+3) square, so memory is O(n^2). For n = 2000 that is about 32 MB, which matches the 35 MB measured. If a judge's memory limit is smaller than that, this table does not fit, and you need a different approach. Check the limit before you choose this one.

Bitmask states: the claim line game

Now a state that is a set, not a range. Items 0 to n-1 stand in a row. A move claims an item i that is not yet claimed and has no claimed neighbour: neither item i-1 nor item i+1 is claimed. A player who cannot move loses. This is normal play: the last player to move wins.

A natural state is the claimed set, stored as a bitmask. That gives 2^n states, which is about one million for n = 20. The search can do much better with a smaller key, which is the state compression step.

The compressed state

An item is available when it is unclaimed and both of its neighbours are unclaimed. Claiming an item never makes an unavailable item available again, because a claimed item stays claimed and a claimed neighbour stays claimed. So the set of available items decides the rest of the game. Call that set A.

Claiming item i from A changes A in one simple way. Item i leaves A, and so do its two neighbours, i-1 and i+1, because each now has a claimed neighbour. Nothing else changes:

A after claiming i = A minus {i-1, i, i+1}

The memo table is indexed by A, not by the claimed set. The search runs the same way, but it only visits the subsets that can actually be reached from the full row.

A worked example by hand

Take n = 4, so the items are 0, 1, 2 and 3. Start with A = {0,1,2,3}. Write the opponent's result for each reply.

• Claim 0: A becomes {2,3}. From {2,3}, claim 2 removes {1,2,3}, so A becomes empty and the player who just moved wins. So {2,3} is a win for the player to move. Claiming 0 hands the opponent a win.
• Claim 1: A becomes {3}. The opponent claims 3 and wins.
• Claim 2: A becomes {0}. The opponent claims 0 and wins.
• Claim 3: A becomes {0,1}. From {0,1}, claim 0 removes {0,1}, so A becomes empty and the player who moved wins. So {0,1} is a win for the player to move. Claiming 3 hands the opponent a win.

Every first move leaves the opponent a win, so the first player loses. The program below prints LOSE for n = 4, which matches.

Worked problem: Claim queries

There are T queries. Each query gives one n. For each query, print WIN if the first player wins with perfect play and LOSE otherwise.

Input:

• Line 1: T, with 1 at most T at most 300.
• The next T lines: one n, with 1 at most n at most 20.

Output: T lines, each WIN or LOSE.

Sample input:

6
1
4
8
12
16
20

The solution

The memo is an array of 2^n bytes, indexed by the available set. The value 0 means not yet computed, 1 means the player to move wins and 2 means the player to move loses. The array is reset for each query, so no answer carries over from a row of a different length.

#include <bits/stdc++.h>
using namespace std;
 
// Solution for the claim line problem: one answer per query n.
// Memo is indexed by the available-set bitmask, so each query uses an array of 2^n bytes.
static int n;
static vector<unsigned char> memo;
 
static bool win(uint32_t avail) {
    if (avail == 0) return false;
    unsigned char &slot = memo[avail];
    if (slot) return slot == 1;
    bool res = false;
    for (int i = 0; i < n && !res; ++i) {
        if (!(avail >> i & 1)) continue;
        uint32_t remove = 1u << i;
        if (i > 0) remove |= 1u << (i - 1);
        if (i + 1 < n) remove |= 1u << (i + 1);
        if (!win(avail & ~remove)) res = true;
    }
    slot = res ? 1 : 2;
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        cin >> n;
        memo.assign(1u << n, 0);
        cout << (win((1u << n) - 1) ? "WIN" : "LOSE") << "\n";
    }
    return 0;
}

Real output on the sample, compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0 (no warnings):

WIN
LOSE
LOSE
WIN
WIN
LOSE

The output for n = 4 is LOSE, which matches the hand example. The output for n = 1 is WIN, because the single item can be claimed and the opponent then has no move.

How it was tested

The brute force searches over the claimed set itself, with no compression and no memo, and it is a separate program. The solution agreed with the brute force for every n from 1 to 18, and on 300 random queries with n from 1 to 14, with 0 mismatches. The brute force finished in about 0.12 seconds for n = 20, a losing position, which needs the whole tree to be searched.

Here is the number of states that the single-query solver visited, measured by a counter in the code. For n = 20, it visited 4267 of the 1,048,576 claimed-set masks. For n = 18, it visited 1149 of 262,144. These counts are from one run on one machine, and the exact numbers depend on the order of the search.

Complexity

Each state costs O(n) work to scan its items. The worst case is one state per mask, so the bound is O(n * 2^n) time and 2^n bytes of memory per query. The measured run is far below that bound. For 300 queries with n = 20, the program took 0.08 seconds and used 4.9 MB, as measured by /usr/bin/time -v.

Python version

Python is fast enough for both ideas on small sizes. The sample below runs the crate DP on two rows, and the claim game for n from 1 to 12. It is self-contained and needs no input. The crate DP recurses n levels deep, so keep n in the low hundreds, and keep the claim game at n up to 20.

Real output of that program, run with Python 3.14.4:

crate [3, 9, 1] diff: 11
crate [4, 1, 7, 2, 9] diff: 9
claim outcomes n=1..12: W W W L W W W L W W W W

The Python results match the C++ results: the crate values agree, and the claim outcomes for n from 1 to 12 agree with the C++ solver run on each n. The recursion depth grows with n, so keep n small in Python. The Python timing was not measured on large inputs, so use the C++ version for contest sizes.

Common mistakes

The sign error. The lead flips at each turn, so the recurrence subtracts the opponent's value. A version that adds it instead of subtracting it gives a plausible but wrong result. Here is the output of such a version on the input 3 9 1, next to the correct one:

wrong: diff 13
wrong: mover 13 other 0
 
right: diff 11
right: mover 12 other 1

The wrong version says the second player scores nothing. That cannot be right on this input, because the first player has no move that takes all three crates, so the second player always takes at least one crate with a positive value. The fix is to subtract f(s after m) and to check the sign on 3 9 1 before anything else.

Plain recursion without a memo. The brute force for the crate game has no memo. Its running time grows fast with n. It took 0.43 seconds wall time at n = 18 and 57 seconds at n = 24, on a random input, on this machine. Doubling the input does not double the work. A memo on the state turns the same search into a table walk, which is what the solver does. Time the brute force on your machine before you decide that a solution is fast enough.

Forgetting the empty state. The base case says that with no crates left the lead is 0. If that case returns a different value, every line that reaches an empty state is off. The claim game shows the effect. Change the base case so that an empty available set counts as a win for the player to move, and run n = 1. The program prints LOSE, but one item can be claimed, so the first player should win. The correct output is WIN. Test the base case with the smallest input first.

Using int for the score. The sums can reach 2 times 10^9 when n = 2000 and each crate is near 10^6, which is past the limit of a 32-bit int. Use long long for every total and every difference.

Using the claimed set as the memo key when a smaller key exists. The claimed set works, but it visits many more states than the available set. The compressed key cuts the number of states, which the counter in the claim solver shows. Check the key by asking whether two states with the same key have the same future moves.

Checklist to keep

• Name the state before you write any code. If two different situations share a key, the key is wrong.
• Write the recurrence with the sign on the opponent's value, and check it on a three-item input by hand.
• The base case for no moves is 0 for a score difference and "player to move loses" for a win or lose game.
• Memo every state that the recursion can reach, and check that the memo array has the right size.
• Use long long for totals and differences.
• Keep a brute force for small inputs, and compare the two on random inputs before you trust the solver.

Hands-on exercise

Work in your own scratch folder. Write the crate game twice: once as the top-down memo in the standard technique, and once as a brute force that recurses on a plain list, with no memo. Run both on 300 random inputs with n from 1 to 11 and values from 0 to 20. Print any input where they disagree.

Then change the claim game so that a claimed item blocks only its right neighbour, not its left neighbour. Write the new rule for the available set, then check your memo solver against a brute force for n from 1 to 14. A good answer says which items leave the available set when item i is claimed. A weak answer changes the search code without changing the state.

Prompt to try with an AI tool

Use this prompt, then check the answer with the steps above.

Write a C++17 program for this game. A row of n crates, 1 to 2000, with values a_i from 0 to 10^6.
On a turn, the mover takes the leftmost crate, or the two leftmost crates, or the rightmost crate,
and scores the sum of what they took. Both players maximise their own total. Print the best
difference (mover total minus other total) under optimal play. Use a memo on the range of crates
left. Explain in two sentences why the opponent's value is subtracted. Then show the output for
the input 3 9 1.

A good answer subtracts the opponent's value from each move, uses long long, and prints 11 for the last check. Check the sign first. A common wrong answer adds the opponent's value, and the output for 3 9 1 is 13, which the sign check in the mistakes section catches.

Practice

These take a few minutes each. Try them on paper or in your scratch folder before you open the answers.

Practice 1: two crate rows by hand

Compute the best difference for the crate rows 5 1 and 2 2 2.

Hint: For 5 1, there are three moves at the start. For 2 2 2, list the states of length 1 and 2 first.

Show the answer

For 5 1, the best difference is 6. Taking 5 and 1 together scores 6 and leaves nothing. For 2 2 2, the best difference is 2. Taking the two leftmost crates scores 4 and leaves [2], which the opponent takes for 2, so the lead is 4 - 2 = 2. The other two first moves give 2 - 4 = -2 each. The program prints diff 6 for the first row and diff 2 for the second.

Practice 2: the winning first move for five items

Find a first move for the claim line with n = 5 that makes the second player lose.

Hint: Claim an item and find the available set that is left. Then check whether the player to move from that set can win.

Show the answer

Claim item 2, the middle item. It removes items 1, 2 and 3, which leaves the available set {0, 4}. From {0, 4}, a claim of 0 leaves {4}, and a claim of 4 leaves {0}. Each of those single items is a win for the player to move, so either reply lets the first player win on the next move. A brute force check on the full search confirms that claiming item 2 is the only winning first move, because the opponent wins after each of the other four claims.

Practice 3: the compressed state after two claims

For the claim line with n = 6, start with all six items available. Claim item 0, and then claim item 4. Write the available set as a bitmask, with bit i set for item i.

Hint: Use the rule that claiming i removes i-1, i and i+1.

Show the answer

Claiming item 0 removes items 0 and 1, which leaves {2, 3, 4, 5}. Claiming item 4 removes items 3, 4 and 5, which leaves {2}. In bitmask form, that is 0b000100, which is the number 4. The memo key for this position is 4, not the claimed set {0, 4}.

Practice 4: find the sign bug

A program has the line best = max(best, a[l] + d[l + 1][r]); where the correct line subtracts. On the input 3 9 1, what does the program print for diff, and why is the claim that the mover takes everything wrong?

Hint: Compute the first move's value with the wrong line, then ask what the opponent gets.

Show the answer

The wrong program prints diff 13 and mover 13 other 0, as shown in the mistakes section. The line adds the opponent's future lead to the mover's gain, so the mover looks as though the opponent gains nothing. With three crates, the first player cannot take all of them in one move, so the second player always takes at least one crate. The correct fix is to subtract the opponent's value.

Practice 5: memory for the crate table

Estimate the memory for the bottom-up table when n = 2000, and say whether it fits in 64 MB.

Hint: Count the entries in the square table, and multiply by the size of one long long.

Show the answer

The table has (n+3) x (n+3) = 2003 x 2003, which is about 4.0 million entries. Each long long takes 8 bytes, so the table is about 32 MB. The measured maximum resident memory was 35 MB, which includes the program itself. It fits in 64 MB, but only just, so keep the table in one allocation and avoid copies.

Summary

A two-player game with scores becomes a recurrence on the lead. The mover's lead is the gain of a move minus the opponent's best lead from the new state. A memo turns the recursion into a walk over the states, so the cost follows the number of distinct states rather than the number of paths. For win or lose games with set states, the available set is a smaller key than the claimed set, because claimed items never come back. Each C++ program here was checked against a brute force before its output was shown, and the Python sample was checked against the C++ results.

Sources and scope

The score-difference recurrence and the memoised search are standard techniques in competitive programming, and the claim line game is an original rule written for this lesson. Every program was compiled with g++ 15.2.0 using -std=c++17 -O2 -Wall -Wextra and run on Linux, except the Python sample, which ran with Python 3.14.4. The brute force comparisons, the timings and the memory numbers were measured on this machine, and the counts of visited states come from one run with a counter in the code. Other machines and other input orders will give other timings and visit counts. The statement of the crate line problem and the claim queries problem are original to this lesson.