Dice Sum Ways
Medium · rating 1500 · Dynamic Programming, Combinatorics
Roll d ordinary 6-sided dice. Read d and a target s, and print the number of ordered outcomes whose pips add up to exactly s.
Constraints: 1 ≤ d ≤ 20, d ≤ s ≤ 6d
Editorial
Approach
Count ordered outcomes with a rolling DP over the dice. dp[t] holds the number of ways to reach sum t so far; adding a die replaces it with, for each face 1–6, the ways that were face less.
dp = [1] + [0]*target
for _ in range(d):
nd = [0]*(target+1)
for cur, ways in enumerate(dp):
for face in range(1, 7):
if cur+face <= target: nd[cur+face] += ways
dp = ndComplexity
Time: O(d · target · 6). Space: O(target).
Related problems
- Unique Grid Paths — Hard
- Balanced Bracket Count — Hard
- House Robber — Hard
- Staircase With K Steps — Medium
- Longest Increasing Subsequence — Hard
- Maximum Product Subarray — Hard