DSA sheet / Dynamic programming
Dice Combinations
Do these first: Bit Strings
The problem in brief
You throw a standard six-sided die as many times as you like. Given a target n (up to a million), print how many different sequences of throws add up to exactly n, modulo 10^9 + 7. Different orders count as different sequences.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1633.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Ask about the last throw. What are the possible values it could have had?
-
If the last throw was a d, what is left to be made by the throws before it?
-
Let ways[s] be the number of sequences summing to s. Write ways[s] in terms of smaller entries of the same array, and decide what ways[0] should be.
-
The numbers explode, so reduce modulo 10^9 + 7 as you go. Which order do you fill the array in?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Counting sequences is the moment to think “recurrence”. Direct enumeration (try every sequence) explodes, and the number of sequences is astronomically large. What rescues you is the shared structure: every sequence ending in throw d is a sequence for the smaller total s - d followed by d. So the count for total s is the sum of the counts for s - 1, …, s - 6, and that only refers to smaller totals.
This is the DP recipe: define the state (ways to reach total s), find the transition (condition on the last step), fix the base case (one way to make 0: the empty sequence), and choose an evaluation order (increasing s). Without the base case the whole table is zero, so always say aloud what the empty case is.
Intuition
Climbing a staircase where each move is 1 to 6 steps: the number of ways to reach step s is the sum of the ways to reach the six steps below it, because you must have arrived from one of them.
Approach
- Create ways[0..n], set ways[0] = 1.
- For s from 1 to n: ways[s] = sum of ways[s - d] for d = 1..6 with s - d >= 0, all modulo 10^9 + 7.
- Print ways[n].
Pitfalls: take the modulus after adding the (up to six) terms, using 64-bit for the sum; do not go below index 0; n = 1 gives 1. An array of a million 32-bit ints is only 4 MB.
Complexity
O(6n) = O(n) time, O(n) memory (a rolling window of six values would make it O(1)).
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
const long long MOD = 1000000007LL;
vector<int> ways(n + 1, 0);
ways[0] = 1;
for (int s = 1; s <= n; s++) {
long long total = 0;
for (int d = 1; d <= 6 && d <= s; d++) total += ways[s - d];
ways[s] = total % MOD;
}
printf("%d\n", ways[n]);
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
MOD = 10**9 + 7
ways = [0] * (n + 1)
ways[0] = 1
for s in range(1, n + 1):
total = 0
for d in range(1, 7):
if d <= s:
total += ways[s - d]
ways[s] = total % MOD
print(ways[n])
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
final long MOD = 1_000_000_007L;
long[] ways = new long[n + 1];
ways[0] = 1;
for (int s = 1; s <= n; s++) {
long total = 0;
for (int d = 1; d <= 6 && d <= s; d++) total += ways[s - d];
ways[s] = total % MOD;
}
System.out.println(ways[n]);
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
const MOD = 1000000007;
const ways = new Array(n + 1).fill(0);
ways[0] = 1;
for (let s = 1; s <= n; s++) {
let total = 0;
for (let d = 1; d <= 6 && d <= s; d++) total += ways[s - d];
ways[s] = total % MOD;
}
console.log(ways[n]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).