Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
思路：DP
dp[i]表示10^i以内的结果数。则10^0 = 1，则dp[0] = 0（只有0一个数），dp[1]=dp[0] + 所有非零的个位数=10.
则dp[i] = dp[i-1] + i位数中的结果数。
求i位数中的结果数很简单。假设我们要求所有3位数中满足要求的数，则最高位只可能是1到9这9个数，因为每一位不能重复，则次高位只能用0到9中没被用过的数共9个，第三位只能用剩下没被用过的0到9中的8个数，因此总数是9 * 9 * 8。 对于i来说，是9 * 9 *...*(11 - i).
1 class Solution {
2 public:
3 int countNumbersWithUniqueDigits(int n) {
4 if (n == 0) return 1;
5 int res = 10;
6 for (int i = 2; i <= std::min(10, n); i++) {
7 int temp = 9;
8 for (int j = 9; j >= 11 - i; j--)
9 temp *= j;
10 res += temp;
11 }
12 return res;
13 }
14 };