Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Dice Combinations

LeetCode #377Medium

dp[i] = Σ dp[i−j] for j in 1..6 · a 6-wide window

Count the number of ways to reach the sum n by throwing a six-sided die one or more times. Each throw yields a value from 1 to 6, and order matters — for n = 3 the four ways are 1+1+1, 1+2, 2+1 and 3. Return the count modulo 10^9+7.

Asked atAmazonGoogleMeta

Brute force · recursion

time O(6ⁿ)space O(n)

step 1 / 16

[0][1][2][3][4][5][6][7][8]

Brute force · recursion


▸
1ways(s):
2    if s = 0: return 1          // the empty sequence
3    total ← 0
4    for j ← 1 to 6:
5        if j <= s:
6            total ← total + ways(s − j)
7    return total                // recomputes the same s repeatedly

state

n8
faces1..6
ways(0)1

line 1Think about the LAST throw. Whatever it showed — 1, 2, 3, 4, 5 or 6 — everything before it had to sum to n minus that face. So ways(n) = ways(n−1) + ways(n−2) + … + ways(n−6), with ways(0) = 1 for the empty sequence. For n = 3 that gives 4: 1+1+1, 1+2, 2+1, 3.