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

Problem Statement

Consider a game where a player can score 3, 5, or 10 points in one move. Given a total score n, find the number of distinct ways to reach that score. Two ways are different only if the sequence of points scored is different in terms of the combination (not permutation — order doesn't matter).

Example:

• Input: n = 20
• Output: 4 (Ways: 10, 10, 5, 5)

Noob-Friendly Explanation

Imagine you're playing a game where you can score either 3 points, 5 points, or 10 points each turn. You want to reach exactly n points total. How many different combinations of moves can get you there? Note: scoring 3 then 5 is the SAME as scoring 5 then 3 — we only count unique combinations, not arrangements.

Approach 1: Brute Force

Intuition

Use recursion to try all combinations. To avoid counting permutations, ensure we pick scores in non-decreasing order — always process 3s first, then 5s, then 10s.

Algorithm

1. Define a recursive function with the remaining score and the minimum allowed score.
2. If remaining score is 0, we found a valid way.
3. Try each score (3, 5, 10) that is ≥ the minimum allowed, and recurse.

class Solution {
    public static int countWaysBrute(int n, int minScore) {
        if (n == 0) return 1;
        if (n < 0) return 0;

        int ways = 0;
        int[] scores = {3, 5, 10};

        for (int score : scores) {
            if (score >= minScore) {
                ways += countWaysBrute(n - score, score);
            }
        }

        return ways;
    }

    public static void main(String[] args) {
        System.out.println(countWaysBrute(20, 3)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(3^(n/3)) - at most n/3 levels of recursion, each branching up to 3 ways
• Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

This is a variant of the coin change problem. Use a 1D DP array where we process each score type one at a time (to avoid counting permutations). For each score value, update the dp array to count how many ways to reach each total.

Algorithm

1. Create a dp array of size n + 1, with dp[0] = 1 (one way to make 0: do nothing).
2. For each score value (3, 5, 10), iterate from that value to n and update: dp[i] += dp[i - score].
3. Return dp[n].

class Solution {
    public static int countWays(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1; // One way to reach score 0

        // Process score 3
        for (int i = 3; i <= n; i++) {
            dp[i] += dp[i - 3];
        }

        // Process score 5
        for (int i = 5; i <= n; i++) {
            dp[i] += dp[i - 5];
        }

        // Process score 10
        for (int i = 10; i <= n; i++) {
            dp[i] += dp[i - 10];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(countWays(20)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(n) - three passes through the dp array
• Space Complexity: O(n) - the dp array