The Digit DP Template

function solve(N):
    digits = getDigits(N)
    memo = {}
    
    function dp(pos, state, tight, started):
        if pos == len(digits):
            return baseCase(state, started)
        if (pos, state, tight, started) in memo:
            return memo[(pos, state, tight, started)]
        
        limit = digits[pos] if tight else 9
        result = 0
        for d in range(0, limit + 1):
            result += dp(pos + 1, newState, tight and d == limit, started or d > 0)
        
        memo[(pos, state, tight, started)] = result
        return result
    
    return dp(0, initialState, true, false)