Count Numbers with Unique Digits

题目来源
计算1到10^n数字中每一个数字都是唯一的数。
原来以为很复杂，需要一系列推导，没想到结果答案那么简单。

f(0) = 1
f(1) = 10
f(2) = 9 * 9
f(3) = f(2) * 8
f(4) = f(3) * 7
...
f(11) = f(10) * 0 = 0
f(12) = f(13) = ... = 0

当两位数的已经都求出来之后，求三位数，往低位插一个数字，有8种选择。
代码如下：

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        vector<int> dp(n+1, 0);
        if (n == 0)
            return 1;
        if (n == 1)
            return 10;
        if (n == 2)
            return 91;
        dp[1] = 10;
        dp[2] = 81;
        int m = min(n, 10);
        for (int i=3; i<=m; i++)
            dp[i] = dp[i-1] * (11-i);
        int sum = 0;
        for (int i=1; i<=n; i++)
            sum += dp[i];
        return sum;
    }
};

优化之后如下：

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        vector<int> dp(n+1, 0);
        if (n == 0)
            return 1;
        int sum = 10;
        int uniqueDigits = 9;
        int availableNum = 9;
        while (n-- > 1 && availableNum > 0) {
            uniqueDigits = uniqueDigits * availableNum;
            sum += uniqueDigits;
            availableNum--;
        }
        return sum;
    }
};