[数据结构与算法]【数位dp】剑指 Offer 43. 1～n 整数中 1 出现的次数

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

数据范围:1 <= n < 2^31

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

思路

这道题看了数据范围之后我就知道这是我不会的题目了，在leetcode评论区得知这是一道经典数位dp题目后，我就去了解了数位dp的思想，特别是参考了b站大佬对于数位dp思想视频讲解后，豁然开朗，依葫芦画瓢自己写完了这道题

总结思路：

1. 假设n为12345，可将题目转化为在大小为5的num[5]数组中，计算每位num[i]分别取0~9后（即00001-12345），1出现的次数
2. dfs方程 dfs(int pos, int pre, bool flag, vector<vector> &dp, int cnt) 其中pos为当前位置，pre为pos-1位置数值，flag表示位置0 ~ pos-1上的数值是否等于该位置的最大值（如举例中位置0的最大值为1， 位置1的最大值为2），dp为记忆数组，cnt为位置1 ~ pos-1中1的数量

代码

class Solution {
public:
    vector<int> num;
    
    int dfs(int pos, int pre, bool flag, vector<vector<int>> &dp, int cnt){
        if(pos<0)
            return cnt;

        if(flag==false && dp[pos][cnt]!=-1)
            return dp[pos][cnt];

        int n, ans = 0;

        if(flag)
            n = num[pos];
        else
            n = 9;

        for(int i=0; i<=n; i++){
            ans += dfs(pos-1, i, flag && i==num[pos], dp, cnt+(i==1));
        }

        if(flag==false)
            dp[pos][cnt] = ans;

        return ans;
    }

    int countDigitOne(int n) {
        while(n){
            num.push_back(n%10);
            n /= 10;
        }

        int m = num.size()-1, ans = 0;

        vector<vector<int>> dp(m+1, vector<int>(10, -1));

        for(int i=0; m>=0&&i<=num[m]; i++)
            ans += dfs(m-1, i, num[m]==i, dp, i==1);

        return ans;
    }
};