Digit DP

public int countNumbersWithDigitSum(int n, int k) {
    String s = String.valueOf(n);
    int len = s.length();
    int[][] memo = new int[len][k+1]; // [position][remaining sum]
    // -1 = uncomputed; only valid when tight=false
    for (int[] row : memo) Arrays.fill(row, -1);
    return dp(s, 0, k, true, memo);
}

int dp(String s, int pos, int remainingSum, boolean tight, int[][] memo) {
    if (remainingSum < 0) return 0; // exceeded sum limit
    if (pos == s.length()) return 1; // valid number found

    if (!tight && memo[pos][remainingSum] != -1)
        return memo[pos][remainingSum];

    int limit = tight ? (s.charAt(pos) - '0') : 9;
    int count = 0;
    for (int digit = 0; digit <= limit; digit++) {
        count += dp(s, pos + 1, remainingSum - digit,
                    tight && digit == limit, memo);
    }

    if (!tight) memo[pos][remainingSum] = count;
    return count;
}

public int countWithoutDigit(int n, int forbidden) {
    String s = String.valueOf(n);
    int[][] memo = new int[s.length()][2]; // [pos][hasLeadingZero]
    for (int[] row : memo) Arrays.fill(row, -1);
    return dp(s, 0, true, false, forbidden, memo);
}

int dp(String s, int pos, boolean tight, boolean leadingZero,
       int forbidden, int[][] memo) {
    if (pos == s.length()) return leadingZero ? 0 : 1;
    int key = tight ? -1 : (leadingZero ? 1 : 0); // simplified
    // Full memoization needs tight=false

    int limit = tight ? (s.charAt(pos) - '0') : 9;
    int count = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == forbidden && !leadingZero) continue;
        count += dp(s, pos + 1, tight && d == limit,
                    leadingZero && d == 0, forbidden, memo);
    }
    return count;
}

// Most digit DP problems ask about range [lo, hi]
// Use: count(hi) - count(lo - 1)

public int countInRange(int lo, int hi) {
    return count(hi) - count(lo - 1);
}

// Count numbers ≤ n where all digits are distinct
public int countNumbersWithUniqueDigits(int n) {
    // Special case: n ≤ 10 digits
    String s = String.valueOf(n);
    return dp(s, 0, true, false, 0);
}

int dp(String s, int pos, boolean tight, boolean started, int usedMask) {
    if (pos == s.length()) return started ? 1 : 0;
    int limit = tight ? (s.charAt(pos) - '0') : 9;
    int count = !started ? 1 : 0; // count the number 0 (leading zeros)
    for (int d = started ? 0 : 1; d <= limit; d++) {
        if (started && (usedMask >> d & 1) == 1) continue; // digit already used
        count += dp(s, pos+1, tight && d == limit,
                    true, usedMask | (1 << d));
    }
    return count;
}

State: (position, [...constraints...], tight, leadingZero)
Transition: try placing each valid digit at current position
Base case: pos == len → valid count (1 or 0)
Memoize: when tight=false (and leadingZero handled)