<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:
    vector<int> dp;
    vector<int> count;
    int solve(int n){
        int dig=0;
        int t = n;
        while(t>0){
            dig++;
            t = t/10;
        }
        int ans=0;
        if (n==0) return 0;
        if (dig == 1) return 1;
        ans += dp[dig-1];
        int first = n/pow(10, dig-1);
        ans += (first-1)*dp[dig-1];
        ans += solve(n%(int)pow(10, dig-1));
        if (first == 1){
            ans += n%(int)pow(10, dig-1) + 1;
        }
        else {
            ans += count[dig-1];
        }
        return ans;
    }
    int countDigitOne(int n) {
        int ans=0;
        if (n==0) return 0;
        if (n>=1 && n<=9) return 1;
        dp = vector<int> (11, 0);
        count = vector<int> (11, 0);
        count[1] = 10;
        for(int i=2; i<=9; i++){
            count[i] = pow(10, i);
        }
        dp[1] = 1;
        for(int i=2; i<=9; i++){
            dp[i] += 10*dp[i-1];
            dp[i] += count[i-1];
        }
        dp[10] = dp[9]+1;
        if (n == 1000000000) return dp[10];
        int dig=0;
        int t = n;
        while(t>0){
            dig++;
            t = t/10;
        }
        ans = solve(n);

        return ans;
    }
};
7400