233. 数字 1 的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0

提示：
0 <= n <= 109

思路：
数位DP(不用管前导0)

// 递推型
class Solution {
    public int countDigitOne(int n) {
        //数位dp
        //预处理
        int[] f = new int[10];
        int[] pow = new int[10];
        f[0] = 0;
        pow[0] = 1;
        for (int i = 1; i < 10; i++) {
            // 统计低位 和 当前位 1 出现的次数
            f[i] = f[i - 1] * 10 + pow[i - 1];
            pow[i] = pow[i - 1] * 10;
        }
        List<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(n % 10);
            n /= 10;
        }
        int res = 0, last = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            //先统计前面的1可能出现的次数
            res += last * x * pow[i];
            if (x == 1) {
                last++;
                res += f[i];
            } else if (x != 0) {
                res += pow[i] + f[i] * x;
            }
        }
        return res + last;
    }
}

// 记忆化搜索模板
class Solution {
    int[][] f = new int[10][10];
    List<Integer> num = new ArrayList<>();
    public int countDigitOne(int n) {
        while (n > 0) {
            num.add(n % 10);
            n /= 10;
        }
        for (int i = 0; i < 10; i++)
            Arrays.fill(f[i], -1); 
        return dfs(num.size() - 1, 1, 0);
    }
    int dfs(int cur, int lim, int pre) {
        if (cur == -1) return pre;
        int ans = f[cur][pre];
        if (lim != 1 && ans >= 0) return ans;
        ans = 0;
        for (int x = 0; x <= (lim == 1 ? num.get(cur) : 9); x++) {
            if (lim == 1 && x == num.get(cur))
                ans += dfs(cur - 1, 1, pre + (x == 1 ? 1 : 0));
            else ans += dfs(cur - 1, 0, pre + (x == 1 ? 1 : 0));
        }
        if (lim != 1) f[cur][pre] = ans;
        return ans;
    }
}