<p>Given an integer <code>n</code>, count <em>the total number of digit </em><code>1</code><em> appearing in all non-negative integers less than or equal to</em> <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    int solve(string &num, int index, int less, int count, vector<vector<vector<int>>> &dp){
        if(index==num.size()) return count;

        if(dp[index][less][count]!=-1) return dp[index][less][count];

        int limit=9;
        if(less==0) limit=num[index]-'0';

        int res=0;
        for(int digit=0; digit<=limit; digit++){
            if(digit==1){
                res+=solve(num, index+1, less || (digit<limit), count+1, dp);
            }
            else{
                res+=solve(num, index+1, less || (digit<limit), count, dp);
            }
        } 
        return dp[index][less][count]=res;
    }
    int countDigitOne(int n) {
        string num=to_string(n);
        vector<vector<vector<int>>> dp(num.size(), vector<vector<int>>(2, vector<int>(num.size(), -1)));
        return solve(num, 0, 0, 0, dp);
    }
};
7600