357-计算各个位数不同的数字个数

力扣357

https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

虽然标签时回溯，但是不要回溯，这一看就是数学题

思路：对于n位的数，首位（第一位）不能为0，所以有9种选择（1~9），第二位则有9种选择，第三位8种选择，第四位7种选择…

不考虑首位，从第二位开始，选择数是递减的。最后再乘上首位一定是9种。

当首位为0时，实际上退化为n-1位数，也就是说，变成了动态规划问题，记录dp[n-1]的结果

举个例子：

已知n=1时有0~9，10种情况

n=2：十位不为0(假设取了9)，个位有9种情况(0~8)，个位为0实际上就是n=1的10种情况，res = 9 * 9 + 10 = 91

n=3：百位不为0时有9种，十位有9种，个位有8种，个位为0时实际上就是n=2，res = 9 * (9 * 8) + 91 = 739

n=1：res = 9 * (9 * 8 * 7) + 739

也就是dp了，这种题就属于一开始看不出dp那种

代码如下：

public int countNumbersWithUniqueDigits(int n) {
    if(n == 0) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 10;
    for (int i = 2; i <= n; i++) {
        int time = i, num = 9, product = 1;
        while (--time != 0){
            product *= num;
            num--;
        }
        dp[i] = 9 * product + dp[i - 1];	//最后再乘上首位的9种
    }
    return dp[n];
}