357_计算各个位数不同的数字个数.md

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

问题

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n。

示例

给定 n = 2，返回 91。（答案应该是除[11,22,33,44,55,66,77,88,99]外，0 <= x < 100 间的所有数字）

解答

假设现在已经得到了n=2的结果，那么求解n=3时，就是计算100到999范围内有多少完全不重复的数字。而，这个可以根据10到99范围内有多少不重复数字来计算，因为就是相当于在这些数字后面加上一个digit，而这个digit可以选择的个数是跟n相关的，n越大可以选择的也就越少。

所以，很容易可以得到递推式：dp[i] = dp[i-1] * (10 - i + 1)。

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n < 2) {
            return n == 0 ? 1 : (n == 1 ? 10 : (n == 2 ? 91 : -1));
        }
        int last = 10 - 1;
        int result = 10;
        for (int i = 2; i <= n; ++i) {
            last = last * (10 - i + 1);
            result += last;
        }
        return result;
    }
};