给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
示例:
输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。解题思路：
其实一个二位数就是由一位数后面加一位组成的
如：
一位数：0 1 2 3 4 5 6 7 8 9 二位数：10 11 12 13 14 15 16 17 18 19 1后面加上0~9 20 21 22 23 24 25 26 27 28 29 2后面加上0~9 依次类推因为题目要求每一位数字都不同，依次我们知道，二位数是在一位数的后面再加一个数，它可以选择的数字个数就是10-1,三位数在二位数的前提下加一位数，它可以选择的范围就是10-2
我们用dp[i]表示有i个位的数字中各个位数不同的数的个数，可以得到转移方程如下：
dp[i] = dp[i-1] * (10-i+1)
最后把每一个(1,n)个位中的所有数字累加即可得到答案
代码如下
class Solution { public int countNumbersWithUniqueDigits(int n) { int[] dp = new int[n+1]; int res = 0; if(n<=2) return n==0?1:(n==1?10:91); dp[1] = 10; dp[2] = 81; for(int i=3; i<=n; i++) dp[i] = dp[i-1]*(10-i+1); for(int i=1; i<=n; i++) res += dp[i]; return res; } }时间复杂度为O(n)
空间复杂度为O(n)
