<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:
    def countDigitOne(self, n: int) -> int:
        
        s = str(n)
        ln = len(s)
        dpa = [0]*ln
        dpc = [0]*ln
        dpa[-1] = int(s[-1] != '0')
        dpc[-1] = 1

        tens = 1
        for i in range(ln - 2, -1, -1):
            dig = int(s[i])
            tens *= 10
            dpc[i] = dpc[i + 1]*10 + tens
            dpa[i] = dpa[i + 1]
            if dig == 1:
                dpa[i] += dpc[i + 1] + int(s[i + 1:]) + 1

            elif dig > 1:
                dpa[i] += dig*dpc[i + 1] + tens
        

        return dpa[0]

16300