数位 DP

概念讲解

什么是数位 DP？

数位 DP 是在数位上进行的动态规划，通常用于统计满足条件的数的个数。

适用场景

  • 统计 [L, R] 中满足条件的数
  • 数位相关约束

框架

1234567891011121314151617181920212223242526int digits[20];
int dp[20][状态];

int dfs(int pos, int state, bool limit) {
    if (pos == 0) return 满足条件;
    if (!limit && dp[pos][state] != -1) return dp[pos][state];
    
    int up = limit ? digits[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos-1, 新状态, limit && i == up);
    }
    
    if (!limit) dp[pos][state] = ans;
    return ans;
}

int solve(int n) {
    int len = 0;
    while (n) {
        digits[++len] = n % 10;
        n /= 10;
    }
    memset(dp, -1, sizeof(dp));
    return dfs(len, 初始状态, true);
}

经典问题

不含连续 1 的数

1234567891011121314int dfs(int pos, int last, bool limit) {
    if (pos == 0) return 1;
    if (!limit && dp[pos][last] != -1) return dp[pos][last];
    
    int up = limit ? digits[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++) {
        if (last == 1 && i == 1) continue;  // 不能连续 1
        ans += dfs(pos-1, i, limit && i == up);
    }
    
    if (!limit) dp[pos][last] = ans;
    return ans;
}

考点分析

初赛考查方式

  1. 程序阅读： 数位 DP
  2. 编程题： 数位统计

常见考点

  • 数位 DP 框架
  • 记忆化搜索
  • limit 限制

练习题

  1. 数位 DP 的适用场景？
查看答案

数位 DP 的适用场景：

  1. 统计 [L, R] 中满足条件的数的个数
  2. 数位相关约束：如不含连续 1、数字和为偶数等
  3. 大范围统计：R 可以很大（如 101810^{18}）
  1. limit 的作用是什么？
查看答案

limit 表示当前是否受到上界限制。

  • limit = true：当前位最大只能填 digits[pos]
  • limit = false：当前位可以填 0~9

只有 limit = false 时才记忆化，因为 limit = true 的状态不会重复出现。

  1. 数位 DP 的时间复杂度？
查看答案

O(log⁡R×状态数×10)O(\log R \times \text{状态数} \times 10)

  • log⁡R\log R：数位长度
  • 状态数：取决于具体问题
  • 10：每位枚举 0~9

易错点

⚠️ 注意：

  1. 只在 limit=false 时记忆化
  2. 注意前导零
  3. 状态要包含足够信息
  4. 用记忆化搜索实现