<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>

vector<int> powers{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
class Solution {
public:
    int recur(int index, bool flag, string &num, vector<vector<int>> &dp) {
        if(index == num.size()) return 0;
        if(dp[index][flag] != -1) return dp[index][flag];
        int answer = 0;
        char limit = num[index];
        if(!flag) limit = '9'+1;
        for(char dig = '0'; dig < limit; dig++) {
            if(dig == '1') answer += powers[num.size() - index - 1];
            answer += recur(index+1, false, num, dp);
        }
        if(flag) {
            if(num[index] == '1') {
                int partNumber = stoi(num) - stoi(num.substr(0, index+1) + string(num.size()-1-index, '0'))+1;
                // cout << index << " " << partNumber << endl;
                answer += partNumber;
            }
            answer += recur(index+1, true, num, dp);
        }
        return (dp[index][flag] = answer);
    }
    int countDigitOne(int n) {
        string num = to_string(n);
        vector<vector<int>> dp(num.size(), vector<int> (2, -1));
        return recur(0, true, num, dp);
    }
};
8000