320. Count Ways to Reach a Given Score in a Game

In a game, a move scores exactly 3, 5, or 10 points. Given a target total score, count the number of distinct ways (as unordered combinations of moves - the same multiset of move values counted once regardless of order) to reach exactly that score.

Input: The input is a single line containing the integer target score. Output: Print a single integer - the number of distinct ways (as combinations, order-independent) to reach exactly that score using moves worth 3, 5, or 10.

0 <= score <= 10^4

A score of 0 counts as exactly ONE way (making no moves at all) - this base case (dp[0]=1) is what correctly seeds the whole counting process, not 0 ways as might be intuitively assumed.

Count the number of distinct ways to reach a target score using moves worth 3, 5, or 10 points. Brute force: Try every possible sequence of moves directly, tracking which combinations reach exactly 20 - this risks double-counting the same combination in different move orders unless carefully deduplicated. Optimised: This is a direct, minimal restatement of 'Coin Change - Count Number of Ways' with a fixed 3-element coin set - the identical coin-outer-loop technique applies directly, guaranteeing each distinct combination of moves is counted exactly once.

Use a 1D array dp of size score+1 initialized with dp[0] = 1, and for each move value in turn (3, then 5, then 10), update dp[j] += dp[j - move] for j from move up to score, processing move types in the outer loop and amounts in the inner loop - the standard 'combinations, not permutations' coin-change counting trick, since it counts each distinct multiset of moves exactly once. This is fully iterative, avoiding recursion overhead entirely, and reaches the same result as the memoized version with a simpler, cache-friendly loop. Time: O(score * 3) = O(score) Space: O(score)

Use the same recursive structure - at each step either use the current move value again or move on to the next smaller move value - but cache results keyed by (remaining score, current move index) so that once a state's number of ways has been computed it's never recomputed. Since there are only score * 3 possible states, this collapses the exponential recursion tree down to a linear number of actual computations. Time: O(score) Space: O(score)

Recursively consider the moves in a fixed order (3, then 5, then 10) and, at each step, either use one more of the current move value or move on to consider only the remaining smaller move values, subtracting the move value from the target score until it hits exactly zero (a valid way) or goes negative/runs out of move types (invalid). This explores every combination of move counts, but without any caching, the same remaining-score-and-move-index states are recomputed repeatedly, causing exponential blowup. Time: O(2^score) roughly (exponential without memoization) Space: O(score)

1. This is exactly coin-change 'count ways' with a FIXED coin set of {3,5,10}: dp[s] = ways to reach score s; dp[0]=1. 2. Process ONE move value at a time (3, then 5, then 10), updating dp[s] += dp[s-move] for every s >= move in increasing order. 3. This coin-by-coin processing order is exactly what avoids counting the same combination in multiple different orders.

Time: O(3 * score) - three move values, each updating all reachable scores. Space: O(score), for the dp array.

Test score = 0 (exactly one way: no moves), a score unreachable by any combination of 3/5/10 (answer 0), and score at the upper bound of 10^4.

Be ready to immediately recognize this as coin-change-count-ways in disguise - the framing (game moves instead of coins) is different, but the underlying DP technique is identical.