# -*- coding: utf-8 -*-
# @Author  : LG

"""
执行用时：36 ms, 在所有 Python3 提交中击败了85.03% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了93.39% 的用户

解题思路：
    动态规划
        0 <= x < 10**n, x为最大n位数
        m       num             说明
        1位数     10          0,1~9
        2位数     9*9         第一位9个：1~9 第二位10-1个：0~9
        3位数     9*9*8       第一位9个：1~9 第二位10-1个：0~9 第三位10-2个0~9
        4位数     9*9*8*7     第一位9个：1~9 第二位10-1个：0~9 第三位10-2个0~9 第四位10-3个0~9
        5位数     9*9*8*7*6
        6位数     9*9*8*7*6*5
        7位数     9*9*8*7*6*5*4
        8位数     9*9*8*7*6*5*4*3
        9位数     9*9*8*7*6*5*4*3*2
        10位数    9*9*8*7*6*5*4*3*2*1
"""
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        dp = [0 for _ in range(10)]
        dp[:3] = [1, 9, 81]
        for i in range(3,10):
            dp[i] = dp[i-1]*(10-i+1)
        if n > 9:
            n = 9
        return sum(dp[:n+1])