Dynamic Programming • Combinatorics

Digit DP

Count the number of integers in a range `[L, R]` that satisfy a certain property using digit-by-digit construction.

Overview

Instead of iterating all numbers in `[L, R]`, we construct numbers digit by digit. To solve for `[L, R]`, we typically compute `solve(R) - solve(L-1)`.

The 'Tight' Bound

A boolean variable `tight` tracks if the digits chosen so far match the prefix of `R`. If true, the next digit cannot exceed the next digit of `R`.

Memoization

Once `tight` becomes false (we picked a smaller digit), the choices for remaining digits are entirely unconstrained and can be heavily reused (memoized).

Key Insight

The state usually looks like `dp[idx][tight][other_constraints]`. The number of states is extremely small relative to the value of `R` (logarithmic).

Recursive Construction Tree (Limit: 32)

Idx: 0
Tight: True

➡

Idx: 1
Tight: True

➡

Idx: 2
Base Case

Code Tracker

:::

1function solve(idx, tight) {

2 if (idx === n) return 1;

3 if (dp[idx][tight] !== -1) return dp[idx][tight];

4 let limit = tight ? parseInt(str[idx]) : 9;

5 let ans = 0;

6 for (let d = 0; d <= limit; d++) {

7 ans += solve(idx + 1, tight && (d === limit));

8 }

9 return dp[idx][tight] = ans;

10}

Digit Dp

Digit Dp

Digit DP

Overview

The 'Tight' Bound

Memoization

Key Insight

Digit DP

Overview

The 'Tight' Bound

Memoization

Key Insight