Road Map

数位 dp

数位 DP 问题往往都是这样的题型，给定一个闭区间 [l, r]，让你求这个区间中满足 某种条件 的数的总数。

数位 dp 用来处理计数问题

例题：计算 1 到 N 中 2 出现的次数

算法思路：

求 2 在每一位上出现的次数，求和

假设 我们有 求 1 ~ abcdef 中出现 2 的次数，我们先求 位置 d 出现 2 的次数；

分情况讨论， 假设位置 d 的下标为 i, i 从低位向高位 从 0 递增；此时 $d=A[i] = A[2]$ 如果 $d < 2$ , 前缀 abc 可以取到的范围是$[0, abc-1]$ 共 abc 种情况，后缀可以取到 $[00..0, 99..9]$ 种情况 共 $10^i$ 种情况 如果 $d==2$ , 前缀取 [0, abc-1] 时后缀 取$[00..0, 99..9]$；前缀 = abc 时，后缀可以 取 $[00..0, ef]$ 共 $ef + 1$ 种情况； 如果 d>2, 前缀取 $[0, abc]$共 $abc +1$ 种情况，后缀 取$[00..0, 99..9]$

代码实现

class Solution {
public:
    int numberOf2sInRange(int num) {
        int ans = 0;
        int n = 0;
        int tmp = num;
        while (tmp)n++, tmp/=10; // 获取num的位数
        for (int i = 0; i< n;i++){
            int k = num / (int)pow(10, n-i-1) %10;
            if (k > 2) {
               int f = num / (int)pow(10, n-i) + 1;
               int b = pow(10, n-i-1);
               ans += f * b;
            } else {
                int f = num / (int)pow(10, n-i);
                int b = (int)pow(10, n-i -1);
                ans += f * b;
            }
            if (k == 2) ans += num % (int)pow(10, n-i-1) + 1;
        }
        return ans;
    }
};