357. 统计各位数字都不同的数字个数

357. 统计各位数字都不同的数字个数

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。

示例 1：

输入：n = 2输出：91解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例 2：

输入：n = 0输出：1

 

看到了想用全排列试试看的，果断超时……

看了看题解，用的dp，大佬们真的太强了

class Solution:

    def countNumbersWithUniqueDigits(self, n: int) -> int:

        dp=[0]*10

        dp[0]=1

        dp[1]=10

        for i in range(2,10):

            dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1))

        return dp[n]

题解在这里：

n=0，数字有{0}1个。

n=1，数字有{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}10个。

n=2，数字包括两部分之和，一部分为n=1的所有10个答案，另一部分为长度为2的新增数字。长度为2的新增数字可以在n=1的所有9个数字基础上进行拼接（0不能算）。例如：

从n=1的数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中随便取出一个除0以外的数字（因为0不能作为起始数字！），我们取2好了。通过在2的尾巴处拼接一位数字可以得到新的合法数字有：

{20， 21，23，24，25，26，27，28，29}，

可以看到，除了不能在尾巴处拼接一个2（两个连续的2就非法了！），0-9种一共有9个数字可以拿来拼接在尾巴处。新增答案为9个。同理，对于n=1数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中的其他任意非0数也可以进行拼接操作，一共可以新增9*9个答案。

最终，n=2的合法数字，n=1时的答案 + 长度为2的数字个数（9*9个）= 10 + 81 = 91。

n=3时同理，只不过此时可以用拼接的数字减少为了8个，此时答案为10 + 9 * 9 + 9 * 9 * 8 = 739。

n=4时同理，只不过此时可以用拼接的数字减少为了7个，此时答案为10 + 9 * 9 + 9 * 9 * 8 + 9 * 9 * 8 * 7 = 5275。

通过归纳不难得到，假设 dp[i] 即 n = i时的答案，则动态转移方程为：

dp[i] = dp[i-1] + (dp[i-1] - dp[i-2])*(10-(i-1))

转移的初始条件为

dp[0] = 1

dp[1] = 10