Count Ways to Reach a Score in a Game: DP Approach

Dynamic programming counts the unordered ways to reach a target game score in O(n * k) time, where k is the number of distinct move values.

What the Problem Is Asking

A player scores points in discrete moves. Each move contributes a fixed value from an allowed set. Given a target score n and a set of allowed move values, count the number of unordered combinations of moves that sum to exactly n.

With moves {3, 5, 10} and target 10:

• {5, 5} sums to 10. Valid.
• {10} sums to 10. Valid.
• {3, 3, 4}: 4 is not an allowed move. Invalid.

Answer: 2.

The word “unordered” matters. In a combination, {3, 5} and {5, 3} count as one way because they contain the same moves. In a permutation, both orderings count as two distinct ways. The algorithm’s loop order is what decides which one you compute. Getting the loop order wrong is the most common source of wrong answers on this class of placement coding question.

To see the difference concretely: with moves {3, 5} and target 8:

• Combinations: 1 (only {3, 5})
• Permutations: 2 ({3, 5} and {5, 3})

Most game-score problems ask for combinations.

Why Dynamic Programming

Brute force generates every sequence of moves that sums to n. For large n and several move values, the number of sequences is exponential. Worse, it re-derives the same sub-results repeatedly. Every path to score n that passes through score n - 5 recomputes the count for n - 5.

Dynamic programming solves this by storing the result for each sub-problem in a table. dp[j] holds the number of ways to reach score j. Once computed, it is reused directly without recomputation. Both conditions that justify DP are present here: overlapping sub-problems (many paths reuse the same intermediate scores) and optimal sub-structure (the count for j depends only on counts for smaller scores already in the table).

The resulting algorithm runs in O(n * k) time instead of exponential time, and uses O(n) space for the table.

The DP Recurrence

The recurrence has two parts.

Base case:

• dp[0] = 1: there is exactly one way to reach score zero, which is to take no moves.

Transition:

• For each move value m in the allowed set:
  • For each score j from m to n:
    • dp[j] += dp[j - m]

The reasoning: if there are dp[j - m] ways to reach score j - m, then each of those ways can be extended by one move of value m to reach score j. Summing over all moves gives the total count.

Why outer-moves, inner-scores gives combinations: Processing move m in a single pass over all scores from m to n ensures that move m is considered before any subsequent move. A combination like {3, 5} gets counted once during the pass for move 3 (which builds up dp[8] via dp[5]). The subsequent pass for move 5 never re-adds the {5, 3} ordering because the move-3 pass has already been completed. The two orderings collapse into one count.

If you swap the loops (outer = scores, inner = moves), every ordering is counted separately, producing the permutation count.

Step-by-Step Trace

Target n = 10, allowed moves = {3, 5, 10}. The dp array has indices 0 through 10.

Initial state

j	0	1	2	3	4	5	6	7	8	9	10
dp[j]	1	0	0	0	0	0	0	0	0	0	0

After processing move = 3

For j = 3: dp[3] += dp[0] = 1. For j = 6: dp[6] += dp[3] = 1. For j = 9: dp[9] += dp[6] = 1.

j	0	1	2	3	4	5	6	7	8	9	10
dp[j]	1	0	0	1	0	0	1	0	0	1	0

After processing move = 5

For j = 5: dp[5] += dp[0] = 1. For j = 8: dp[8] += dp[3] = 1. For j = 10: dp[10] += dp[5] = 1.

j	0	1	2	3	4	5	6	7	8	9	10
dp[j]	1	0	0	1	0	1	1	0	1	1	1

After processing move = 10

For j = 10: dp[10] += dp[0] = 1. dp[10] becomes 2.

j	0	1	2	3	4	5	6	7	8	9	10
dp[j]	1	0	0	1	0	1	1	0	1	1	2

Result: dp[10] = 2.

The two unordered combinations are {5, 5} and {10}. No path using move 3 reaches exactly 10 with these allowed values, which the table confirms (no additional contribution to dp[10] from the move-3 pass).

Code

Python

def count_ways(n, moves):
    dp = [0] * (n + 1)
    dp[0] = 1          # base case: one way to reach score 0
    for m in moves:
        for j in range(m, n + 1):
            dp[j] += dp[j - m]
    return dp[n]

# Example: moves {3, 5, 10}, target 10
print(count_ways(10, [3, 5, 10]))   # Output: 2

C

#include <stdio.h>
#include <string.h>

int count_ways(int n, int moves[], int k) {
    int dp[n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;   /* base case */
    for (int i = 0; i < k; i++) {
        int m = moves[i];
        for (int j = m; j <= n; j++) {
            dp[j] += dp[j - m];
        }
    }
    return dp[n];
}

int main() {
    int moves[] = {3, 5, 10};
    printf("%d\n", count_ways(10, moves, 3));   /* Output: 2 */
    return 0;
}

Time and Space Complexity

Space complexity is O(n): the dp array holds n + 1 integers, one per score value from 0 to n. No auxiliary data structures are created beyond this array.

Time complexity is O(n * k) where n is the target score and k is the number of distinct move values. The outer loop runs k times; the inner loop runs at most n steps per iteration. For the problem sizes that appear in placement coding rounds, the solution runs well within standard time limits on any online judge.

One comparison worth noting: the brute-force recursive solution without memoization has exponential time. Adding a memo dictionary converts it to O(n * k) top-down. The bottom-up version above achieves the same complexity without recursion overhead and is the form most placement compilers handle fastest.

Where This Pattern Shows Up

The GeeksforGeeks coin-change counting variant formalises the same recurrence under a different surface framing: coin denominations instead of game-score moves. The structure is identical: dp[0] = 1, outer loop over denominations, inner loop forward over amounts.

This pattern covers a wide class of placement DSA questions tested in TCS NQT Coding and AMCAT Automata rounds: counting step combinations to climb stairs, counting partition ways for a number, counting paths in a grid under move constraints. The equilibrium index of an array uses a related prefix-accumulation idea, where a precomputed table eliminates redundant sub-array sums. Symmetric pairs in an array extends tabular lookup into two-dimensional key matching.

All three share the same design principle: compute once, reuse from the table.

Clearing this kind of coding question means dp[0] = 1, the combination-vs-permutation loop order, and the O(n * k) complexity bound land cleanly before the clock runs out. Once the placement technical round is behind you, TinkerLLM at ₹299 is where learners move to the next layer: building with LLM APIs, a skill set that is increasingly part of the shortlist criteria at product companies beyond the service tier.