Skip to content

Digit DP🔗

Digit DP is used to count or optimize over numbers within a range that satisfy certain properties.

State Parameters🔗

Parameter Meaning
pos Current digit index
tight Whether we’re restricted by upper bound
leading_zero Are we still skipping leading 0s
sum / mask Any custom condition (sum of digits, etc.)

DP Template🔗

int dp[20][2][2];  // pos, tight, leading_zero

int dfs(int pos, bool tight, bool leading_zero, string &num) {
    if (pos == num.size()) return /* base case */;

    if (dp[pos][tight][leading_zero] != -1) return dp[pos][tight][leading_zero];

    int res = 0;
    int limit = tight ? (num[pos] - '0') : 9;

    for (int d = 0; d <= limit; d++) {
        bool new_tight = (tight && d == limit);
        bool new_leading = (leading_zero && d == 0);
        res += dfs(pos + 1, new_tight, new_leading, num);
    }

    return dp[pos][tight][leading_zero] = res;
}

Example: Count numbers with digit sum divisible by k

int k;

int dfs(int pos, int sum, bool tight, string &num) {
    if (pos == num.size()) return (sum % k == 0);

    if (dp[pos][sum][tight] != -1) return dp[pos][sum][tight];

    int res = 0;
    int limit = tight ? (num[pos] - '0') : 9;

    for (int d = 0; d <= limit; d++) {
        res += dfs(pos + 1, (sum + d) % k, tight && (d == limit), num);
    }

    return dp[pos][sum][tight] = res;
}

To count in range [L, R]

int count(string x) {
    memset(dp, -1, sizeof dp);
    return dfs(0, 0, true, x);
}

int answer = count(R) - count(L - 1);

Common Use Cases🔗

  • Count numbers with no repeated digits
  • Count numbers with alternating digits
  • Count palindromes in a range
  • Sum of digits of all numbers in a range

Problems🔗

Digit DP is often implicit in “count how many numbers” problems involving digit constraints.

Easy to Medium

Medium to Hard