Count number of ways to reach a given score in a game

The problem, simply

In a game, one move scores 3, 5 or 10 points. You get a target score n. Count how many different mixes of moves add up to exactly n.

Only the mix matters, not the order. Scoring 3 then 5 is the same mix as 5 then 3, so it counts once.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at the biggest move still allowed. Either score it once more (the target goes down), or decide never to use it again (drop it from the list). Add the counts from both choices.

1. Target 0: one way (count 1).
2. If the biggest allowed move fits, try scoring it.
3. If there is a smaller move left, also try without the biggest move.

class Solution {
    int[] moves = {3, 5, 10};

    // ways to reach rem using only the first k kinds of moves
    long ways(int k, int rem) {
        if (rem == 0) return 1;                        // exact score reached
        long w = 0;
        if (moves[k - 1] <= rem) w += ways(k, rem - moves[k - 1]);   // score it again
        if (k > 1) w += ways(k - 1, rem);                            // never use it again
        return w;
    }

    public long count(int n) {
        return ways(3, n);
    }
}

How long it takes: every call splits in two and the target only drops a little each time, so the calls grow exponentially, up to about O(2^n). Extra room: the chain of calls, O(n).

Way 2: the clever way

Keep one row of boxes, table[0..n]. Box i holds the number of mixes that reach i using the moves allowed so far.

1. table[0] = 1, the rest 0.
2. For move 3, then move 5, then move 10: for i from the move up to n, table[i] += table[i - move].
3. The answer is table[n].

Doing one move kind at a time, in the outer loop, is what makes order not matter.

class Solution {
    public long count(int n) {
        long[] table = new long[n + 1];
        table[0] = 1;                          // reach 0 by doing nothing
        int[] moves = {3, 5, 10};
        for (int move : moves) {               // one kind of move at a time
            for (int i = move; i <= n; i++) {
                table[i] += table[i - move];   // end with this move
            }
        }
        return table[n];
    }
}

How long it takes: three passes over the boxes, O(n). Extra room: the boxes, O(n).

Watch out for

• table[0] must be 1, or every box stays 0.
• Start each pass at i = move, so i - move is never negative.
• The old version of this problem uses int. For large n the counts grow, so use long.

What interviewers ask next

• What if order does matter (a game log, where 3 then 5 differs from 5 then 3)? Swap the loops: scores outside, moves inside. That counts sequences.
• Any list of move values? The code does not change, only the moves array. It is the coin change counting problem.
• Fewest moves to reach n? Use min instead of +: best[i] = min(best[i - move] + 1).
• Can it be done without the array? For only 3, 5 and 10 you can loop over the number of 10s and 5s and check if the rest is a multiple of 3, which is O(n^2 / 50). The array is simpler and faster.

Remember this

Grown-up words: the mixes are combinations, the row of boxes is a 1D DP array, "use it again or never again" is the unbounded knapsack choice, and this is the coin change counting problem with coins 3, 5 and 10.