Pattern Reference
Digit DP
"DP on number digits with tight/loose bounds. Count numbers with property in range. Sum of digits, divisible by k."
Loading...
Deep Dive Tutorial
Digit 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
Digit DP — count valid numbers in [0, N]
// 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 0slightbulb
What goes in "state"?
- 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.
- 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.
Worked Problems
brain
Digit DP state design:
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
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