Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Digit DP
DSA

Digit DP

Understand digit DP for counting or optimizing values under numeric range and digit-based constraints.

Digit DP counts numbers in a range [L, R] that satisfy certain digit-related properties, using stateful DP over digit positions.

Its core advantage:

O(number of digits × tight × sum) — transforms exponential digit enumeration into polynomial DP.

Focus on recognizing:

“Count numbers in range” + “Digit constraints” + “Sum/product of digits” = Digit DP

Generic Digit DP Template (Base)

Digit DP (Count Numbers ≤ N)

Count numbers ≤ 321 whose digit sum is ≤ 5 using digit DP.

State = (position, tight, currentSum). `tight` limits digits to the prefix of N; once we fall below the prefix it's free. Memoize per (pos, sum) when not tight. Each leaf counts a valid number. O(digits·target·10) per tight span.

ARRAY VISUALIZER
Steps –
3
0
2
1
1
2
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        dfs(pos, tight, sum):
                      
                        2
                          if pos == len: return 1 if sum <= target else 0
                      
                        3
                          limit = tight ? digits[pos] : 9
                      
                        4
                          total = 0
                      
                        5
                          for d in 0..limit:
                      
                        6
                            total += dfs(pos+1, tight && d == limit, sum + d)
                      
                        7
                          return total
                      
public int countNumbers(int n, int targetSum) {
    String s = String.valueOf(n);
    int len = s.length();
    int[][][] dp = new int[len][2][targetSum + 1];
    for (int[][] a : dp) for (int[] b : a) Arrays.fill(b, -1);

    return dfs(s, 0, true, 0, targetSum, dp);
}

private int dfs(String s, int pos, boolean tight, int sum, int target, int[][][] dp) {
    if (pos == s.length()) return sum <= target ? 1 : 0;
    if (!tight && dp[pos][tight ? 1 : 0][sum] != -1)
        return dp[pos][tight ? 1 : 0][sum];

    int limit = tight ? s.charAt(pos) - '0' : 9;
    int total = 0;

    for (int d = 0; d <= limit; d++) {
        boolean nextTight = tight && (d == limit);
        if (sum + d <= target)
            total += dfs(s, pos + 1, nextTight, sum + d, target, dp);
    }

    if (!tight) dp[pos][0][sum] = total;
    return total;
}
def countNumbers(n, target_sum):
    s = str(n)

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(pos, tight, sum_so_far):
        if pos == len(s):
            return 1 if sum_so_far <= target_sum else 0

        limit = (
            int(s[pos]) if tight else 9
        )
        total = 0

        for d in range(limit + 1):
            next_tight = tight and (d == limit)
            if sum_so_far + d <= target_sum:
                total += dfs(
                    pos + 1,
                    next_tight,
                    sum_so_far + d
                )

        return total

    return dfs(0, True, 0)
int memo[12][2][100];
string s;
int target;

int dfs(int pos, int tight, int sum) {
    if (pos == (int)s.size()) return sum <= target ? 1 : 0;
    if (!tight && memo[pos][0][sum] != -1)
        return memo[pos][0][sum];

    int limit = tight ? s[pos] - '0' : 9;
    int total = 0;

    for (int d = 0; d <= limit; d++) {
        int nextTight = tight && (d == limit);
        if (sum + d <= target)
            total += dfs(pos + 1, nextTight, sum + d);
    }

    if (!tight) memo[pos][0][sum] = total;
    return total;
}

int countNumbers(int n, int targetSum) {
    s = to_string(n);
    target = targetSum;

    memset(memo, -1, sizeof(memo));

    return dfs(0, 1, 0);
}
function countNumbers(n, targetSum) {
  const s = String(n);

  const memo = new Map();

  function dfs(pos, tight, sum) {
    if (pos === s.length) {
      return sum <= targetSum ? 1 : 0;
    }

    const key = `${pos},${tight},${sum}`;

    if (!tight && memo.has(key)) {
      return memo.get(key);
    }

    const limit = tight ? +s[pos] : 9;

    let total = 0;

    for (let d = 0; d <= limit; d++) {
      const nextTight = tight && d === limit;
      if (sum + d <= targetSum) {
        total += dfs(pos + 1, nextTight, sum + d);
      }
    }

    if (!tight) memo.set(key, total);
    return total;
  }

  return dfs(0, true, 0);
}

Common Mistakes

Tight dimension wrong.

tight tracks whether the prefix matches N — if tight, the current digit is bounded by N[pos]; otherwise 0-9.

Forgetting to mask sum overflow.

Always check sum + d <= target before recursing to avoid out-of-bounds.

Range conversion.

Answer for [L, R] = solve(R) - solve(L - 1).

My Private Notes

Notes are auto-saved locally to this device.