数据结构学习 jz43 数字 1 的个数

关键词：数位dp 记忆化搜索 dfs

专门写了数位dp的笔记，里面的第一题和这个是一模一样的。建议直接看链接。

题目：

复杂度计算：

时间复杂度O(log^2 n)

时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即 O(log^2 n) ，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为 O(log^2 n)

空间复杂度O(log^2 n)?

代码：

class Solution {
public:
    int fun(int pose,bool islimit,int count, vector<vector<int>>& dp)
    {
        if(pose<0) return count;
        if(!islimit&&dp[pose][count]>=0) return dp[pose][count];
        int temp=0;
        int up=islimit?s[pose]:9;
        for(int i=0;i<=up;++i)
        {
            temp=temp+fun(pose-1,islimit&&i==s[pose],count+(i==1),dp);
        }
        if(!islimit)dp[pose][count]=temp;
        return temp;
    }
    int countDigitOne(int n) {
        while(n)
        {
            s.push_back(n%10);
            n=n/10;
        }
        vector<vector<int>> dp(s.size(),vector<int>(s.size()+1,-1));
        return fun(s.size()-1,true,0,dp);
    }
    vector<int> s;
};