Pattern Guide
Digit DP
"Count integers in [0, N] satisfying a digit property."
Digit DP counts numbers in a range [lo, hi] whose digits satisfy some property (digit sum, no consecutive digits, count of specific digits). The technique: count f(hi) - f(lo-1) where f(n) counts valid numbers in [0, n]. Build digit by digit with a "tight" constraint flag.
Problems you can solve with this pattern
4 problems · click any to start solving
// Count integers in [0, N] satisfying some property
// Template: count(N) - count(lo-1)
function digitDP(N) {
const digits = String(N).split('').map(Number);
const n = digits.length;
const memo = new Map();
// pos: current position (0 = most significant)
// tight: are we still bounded by digits of N?
// state: accumulated property state (depends on problem)
function dp(pos, tight, state) {
if (pos === n) return isValid(state) ? 1 : 0;
const key = `${pos},${tight},${state}`;
if (memo.has(key)) return memo.get(key);
const limit = tight ? digits[pos] : 9;
let count = 0;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === limit);
const newState = transition(state, d, pos);
count += dp(pos + 1, newTight, newState);
}
memo.set(key, count);
return count;
}
return dp(0, true, initialState);
}
// For range [lo, hi]: digitDP(hi) - digitDP(lo - 1)
// Handle leading zeros: often pass a 'started' flag or treat them as 0sDigit DP answers questions like "how many integers in [1, N] have a digit sum divisible by k?" or "how many numbers have no two consecutive equal digits?" The key insight: build the number digit by digit from the most significant digit. At each step, track whether we're still "tight" (bounded by N's digits) or "free" (can pick any digit). Memoize on (position, tight_flag, accumulated_state).
The Universal Template
// Count integers in [0, N] satisfying some property
// Template: count(N) - count(lo-1)
function digitDP(N) {
const digits = String(N).split('').map(Number);
const n = digits.length;
const memo = new Map();
// pos: current position (0 = most significant)
// tight: are we still bounded by digits of N?
// state: accumulated property state (depends on problem)
function dp(pos, tight, state) {
if (pos === n) return isValid(state) ? 1 : 0;
const key = `${pos},${tight},${state}`;
if (memo.has(key)) return memo.get(key);
const limit = tight ? digits[pos] : 9;
let count = 0;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === limit);
const newState = transition(state, d, pos);
count += dp(pos + 1, newTight, newState);
}
memo.set(key, count);
return count;
}
return dp(0, true, initialState);
}
// For range [lo, hi]: digitDP(hi) - digitDP(lo - 1)
// Handle leading zeros: often pass a 'started' flag or treat them as 0s- Digit sum problem: accumulated sum so far
- Consecutive digits: last digit placed
- Specific digit count: count of target digit seen
- No two adjacent equal: last digit
- Divisibility: accumulated value mod k
The state must be small enough for memoization. Usually ≤ a few thousand states × 2 (tight flag) × n positions.
1. Always include: position, tight flag
2. Add problem-specific state: last digit, digit sum mod k, digit count, used-mask
3. Handle leading zeros: add a "started" boolean (avoids counting 007 as different from 7)
4. Range query: count(hi) - count(lo-1)
Common state additions:
- No consecutive same digits → last_digit
- Digit sum divisible by k → current_sum_mod_k
- All digits unique → bitmask of used digits (only feasible for small digit sets)
- Count occurrences of digit d → count_so_far