233. Number of Digit One

Tags:

• Hard
• backtrack
• dp
• digit dp
• recommand

Link

I think it might be the easiest digit dp.

There are also mathematical way to solve this question. However, the goal here is learn digit dp and it can be used in many variant questions.

class Solution:
    def countDigitOne(self, n: int) -> int:
        A = list(map(int, str(n)))

        lens = len(A)

        @cache
        def backtrack(i, tight, leading):
            if i == lens:
                return leading
            
            ans = 0

            for d in range(A[i] + 1 if tight else 10):
                    
                ans += backtrack(i+1, tight and d == A[i], leading + (1 if d == 1 else 0))


            return ans

        return backtrack(0, True, 0)