数位 DP (Digit DP)

[!abstract] 核心思想 按数字的每一位进行 DP，通常用于「统计 [0, n] 范围内满足某种条件的数字个数」。

---

模板框架

function digitDP(n: number): number {
  // 1. 将数字转为数字数组
  const digits = n.toString().split('').map(Number);

  // 2. DFS + 记忆化
  const memo: Map<string, number> = new Map();

  function dfs(pos: number, tight: boolean, leadZero: boolean, ...state): number {
    // pos: 当前处理到第几位
    // tight: 是否受上界限制
    // leadZero: 是否有前导零

    // 终止条件
    if (pos === digits.length) return 1;

    const key = `${pos}-${tight}-${leadZero}-${state.join(',')}`;
    if (memo.has(key)) return memo.get(key);

    let ans = 0;
    const limit = tight ? digits[pos] : 9;

    for (let d = 0; d <= limit; d++) {
      const newTight = tight && d === limit;
      const newLeadZero = leadZero && d === 0;

      ans += dfs(pos + 1, newTight, newLeadZero, ...newState);
    }

    memo.set(key, ans);
    return ans;
  }

  return dfs(0, true, true);
}

---

1. 统计 1 的个数

问题

• 1~n 中数字 1 出现的次数

function countDigitOne(n: number): number {
  if (n <= 0) return 0;

  let ans = 0;
  let high = n, cur = 0, low = 0;
  let digit = 1;

  while (high !== 0) {
    high = Math.floor(n / (digit * 10));
    cur = Math.floor((n / digit) % 10);
    low = n % digit;

    // 当前位的贡献
    if (cur === 0) {
      ans += high * digit;
    } else if (cur === 1) {
      ans += high * digit + low + 1;
    } else {
      ans += (high + 1) * digit;
    }

    digit *= 10;
  }

  return ans;
}

// DP 解法
function countDigitOneDP(n: number): number {
  const s = n.toString();
  const digits = s.split('').map(Number);
  const memo: Map<string, number> = new Map();

  function dfs(pos: number, count: number, tight: boolean): number {
    if (pos === digits.length) return count;

    const key = `${pos}-${count}-${tight}`;
    if (!tight && memo.has(key)) return memo.get(key);

    let ans = 0;
    const limit = tight ? digits[pos] : 9;

    for (let d = 0; d <= limit; d++) {
      ans += dfs(pos + 1, count + (d === 1 ? 1 : 0), tight && d === limit);
    }

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

  return dfs(0, 0, true);
}

---

2. 数字游戏

问题

• 给定数字 n，求第 k 小的「幸运数」

function findKthNumber(n: number, k: number): number {
  let cur = 1;
  k--; // 已经选了 cur

  while (k > 0) {
    const steps = getSteps(n, cur, cur + 1);
    if (steps <= k) {
      cur++;       // 移到兄弟节点
      k -= steps;
    } else {
      cur *= 10;    // 移到第一个子节点
      k--;
    }
  }

  return cur;
}

function getSteps(n: number, n1: number, n2: number): number {
  let steps = 0;
  while (n1 <= n) {
    steps += Math.min(n + 1, n2) - n1;
    n1 *= 10;
    n2 *= 10;
  }
  return steps;
}

---

3. 包含特定数字的数

问题

• 统计 1~n 中包含数字 2 的数的个数

function numberCount(n: number): number {
  if (n <= 0) return 0;

  let ans = 0;
  let digit = 1;
  let high = Math.floor(n / 10);
  let cur = n % 10;
  let low = 0;

  while (high !== 0 || cur !== 0) {
    if (cur === 0) {
      // 当前位为 0，不贡献
    } else if (cur === 1) {
      ans += low + 1;
    } else {
      ans += digit;
    }

    // 继续处理高位
    if (high > 0 && cur === 2) {
      ans += low + 1;
    } else if (high > 0 && cur > 2) {
      ans += digit;
    }

    ans += high * digit;

    // 更新
    low += cur * digit;
    cur = high % 10;
    high = Math.floor(high / 10);
    digit *= 10;
  }

  return ans;
}

---

4. 数字和为 K 的数

问题

• 统计 1~n 中各位数字之和等于 k 的数的个数

function numberCountKSum(n: number, k: number): number {
  const digits = n.toString().split('').map(Number);
  const memo: Map<string, number> = new Map();

  function dfs(pos: number, sum: number, tight: boolean): number {
    if (sum > k) return 0;
    if (pos === digits.length) return sum === k ? 1 : 0;

    const key = `${pos}-${sum}-${tight}`;
    if (!tight && memo.has(key)) return memo.get(key);

    let ans = 0;
    const limit = tight ? digits[pos] : 9;

    for (let d = 0; d <= limit; d++) {
      ans += dfs(pos + 1, sum + d, tight && d === limit);
    }

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

  return dfs(0, 0, true);
}

---

5. 不含前导零且数字和为 K

问题

• 统计 [L, R] 范围内数字和为 K 的数的个数

function rangeSum(a: number, b: number, k: number): number {
  return countKSum(b, k) - countKSum(a - 1, k);
}

function countKSum(n: number, k: number): number {
  if (n <= 0) return 0;

  const digits = n.toString().split('').map(Number);
  const memo: Map<string, number> = new Map();

  function dfs(pos: number, sum: number, tight: boolean, leadZero: boolean): number {
    if (sum > k) return 0;
    if (pos === digits.length) return sum === k && !leadZero ? 1 : 0;

    const key = `${pos}-${sum}-${tight}-${leadZero}`;
    if (!tight && memo.has(key)) return memo.get(key);

    let ans = 0;
    const limit = tight ? digits[pos] : 9;

    for (let d = 0; d <= limit; d++) {
      ans += dfs(
        pos + 1,
        sum + (leadZero && d === 0 ? 0 : d),
        tight && d === limit,
        leadZero && d === 0
      );
    }

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

  return dfs(0, 0, true, true);
}

---

6. 经典模板题

洛谷 P2602 - 数字计数

function countDigits(l: number, r: number, target: number): number {
  return countDigit(r, target) - countDigit(l - 1, target);
}

function countDigit(n: number, target: number): number {
  if (n <= 0) return 0;

  let ans = 0;
  let digit = 1;
  let high = Math.floor(n / 10);
  let cur = n % 10;
  let low = 0;

  while (high !== 0 || cur !== 0) {
    if (cur === 0 && target === 0) {
      ans += (high - 1) * digit;
    } else if (cur === 0) {
      ans += high * digit;
    } else {
      ans += high * digit;
      if (target === 0) ans -= digit;
      if (cur > target) ans += digit;
      else if (cur === target) ans += low + 1;
    }

    low += cur * digit;
    cur = high % 10;
    high = Math.floor(hire / 10);
    digit *= 10;
  }

  return ans;
}

---

数位 DP 状态设计

状态	说明	示例
pos	当前位	0~len
tight	是否受上界	true/false
leadZero	是否有前导零	true/false
sum	数字和	0~9*len
cnt	目标数字个数	如 1 的个数
diff	与目标差值	加权求和

---

参见: **DP算法索引** | **DP优化**