Counting ways with modulo
Sum the ways from every predecessor state, mod 1e9+7.
dp[i] counts distinct constructions of the first i positions.
01The intuition
Start with what you would do by hand
The letters A to Z are coded as 1 to 26. The message 226 could be 2 2 6 (BBF), 22 6 (VF) or 2 26 (BZ). How many readings does a digit string have?
By hand you would list them, as above, and get 3. Now try 2222222222, ten digits. Each boundary between digits can be a cut or not, with the rule that a two-digit group must be 10 to 26. Listing by hand gives 89 readings after a lot of care, and for 40 digits the count is in the hundreds of millions, far more than anyone can list. The listing also repeats itself: every reading of the first 8 digits gets written out again for each way of finishing the last 2.
Build the structure, one piece at a time
Count, do not list. Keep an array dp where dp[i] is the number of readings of the first i digits. A reading of the first i digits ends either with a one-digit letter (then the first i − 1 digits were read some way) or with a two-digit letter (then the first i − 2 digits were read some way). Those two groups are different readings, so add them:
| i | prefix | last digit alone | last two digits as one letter | dp[i] |
|---|---|---|---|---|
| 0 | (empty) | 1 | ||
| 1 | 2 | 2 ok → dp[0] = 1 | 1 | |
| 2 | 22 | 2 ok → dp[1] = 1 | 22 ok → dp[0] = 1 | 2 |
| 3 | 226 | 6 ok → dp[2] = 2 | 26 ok → dp[1] = 1 | 3 |
Three readings, as found by hand. The walk-through video uses 1226 and reaches 5. The empty prefix counts as one reading, the "nothing to read" reading; without it the two-digit case at i = 2 would have nothing to add.
The last piece is the modulo. Counts grow fast, so problems ask for the answer modulo 1,000,000,007. Take the remainder after each addition. Because (a + b) mod m = ((a mod m) + (b mod m)) mod m, reducing early never changes the final remainder, and the numbers stay small enough to add safely.
Why it is correct
The invariant: dp[i] equals the number of distinct readings of the first i digits. Every reading of a prefix has a last letter, which uses one or two digits. Readings whose last letter is one digit are in one-to-one correspondence with readings of the prefix one shorter; readings whose last letter is two digits correspond to readings of the prefix two shorter, and only exist when those two digits form a value from 10 to 26 (a leading zero is not a letter). No reading is in both groups, since the last letter has a definite length. So the sum counts each reading exactly once.
dp[i] = [si ≠ 0] · dp[i−1] + [10 ≤ si−1si ≤ 26] · dp[i−2]
Why it is fast
Each cell is one or two additions, so n digits take O(n) steps, and since a cell only looks back two places, two variables are enough memory. Compare with listing: the number of readings itself can be exponential in n (for all 1s and 2s it is a Fibonacci number), so any method that writes them out is exponential, while counting is linear.
How to recognise it in an interview
Cues: "how many ways", "number of distinct", "return the answer modulo 109 + 7". The modulo is the giveaway that the count is huge and you are meant to add counts of smaller cases rather than enumerate. Say: the number of ways to reach state i is the sum of the ways to reach each state that can step to it. Decode Ways is the example. Domino and Tromino Tiling and Knight Dialer are the same shape with different predecessor rules.
02The idea in one line
Sum the ways from every predecessor state, mod 1e9+7.
Reach for it when: Decode ways, unique paths, number of music playlists, dice rolls, count vowels permutation.
Cost: O(n · states) time.
03The walk-through, step by step
The video works one example: Decode Ways on '226'. These are its captions in order, so you can follow without the video or check a step you missed.
- dp[0] = 1: the empty prefix decodes one way
- dp[1]: '1' alone → dp[0] = 1 = 1
- dp[2]: '2' alone → dp[1] = 1 + '12' as one letter → dp[0] = 1 = 2
- dp[3]: '2' alone → dp[2] = 2 + '22' as one letter → dp[1] = 1 = 3
- dp[4]: '6' alone → dp[3] = 3 + '26' as one letter → dp[2] = 2 = 5
- Each dp[i] sums two earlier states; mod keeps the numbers small
- Answer dp[4] = 5: 1,2,2,6 · 12,2,6 · 1,22,6 · 1,2,26 · 12,26
- A Fibonacci-shaped recurrence: O(n) time, two variables of memory
04Asked at Google
7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Count Good Numbers | Medium | 39 | last 6 months |
| Domino and Tromino Tiling | Medium | 35 | last 6 months |
| Decode Ways | Medium | 30 | last 6 months |
| Knight Dialer | Medium | 26 | |
| Number of Dice Rolls With Target Sum | Medium | 20 | last 6 months |
| Number of Ways to Stay in the Same Place After Some Steps | Hard | 18 | |
| Number of Music Playlists | Hard | 5 | last 6 months |
05Related patterns
Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), DP over sorted keys (chains).