Recursion & DP Target: 15s
Digit DP: count numbers up to N with some property. 'tight' tracks if we're still bounded by N's digits.
from functools import lru_cache
def countDigitDP(num):
digits = list(map(int, str(num)))
@lru_cache(maxsize=None)
def dp(pos, tight, started):
if pos == len(digits):
return 1 if started else 0
limit = digits[pos] if tight else 9
res = 0
for d in range(0, limit + 1):
res += dp(pos + 1,
tight and d == limit,
started or d > 0)
return res
return dp(0, True, False)Type it from memory. Go.