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

难度: 🌗

问题描述

---

解法

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        // 思路：
        // 找规律
        // n = 0 --> [0] --> f(0) = 1
        // n = 1 --> [0, 9] --> f(1) = f(0) + {1, ..., 9} 9 种选择 = 10
        // n = 2 --> [0, 99] --> [0, 9] + [10, 99] = f(1) + 9 * 9 = 10 + 81 = 91
        // n = 3 --> [0, 999] --> [0, 99] + [100, 999] = f(2) + 9 * 9 * 8 = 91 + 9 * 9 * 8
        int[] dp = new int[n + 1];
        dp[0] = 1;
        int pre = 9; // 之前的乘积
        for(int i = 1; i <= n; i ++) {
            if(i == 1) {
                dp[i] = dp[i - 1] + pre;
            } else {
                pre *= (11 - i);
                dp[i] = dp[i - 1] + pre;
            }
        }
        return dp[n];
    }
}

---

输出