题目描述:
357. Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
其实这个题目不怎么需要动态规划的知识,感觉有点像找规律填数字。
可以把题目拆开,先思考固定长度为n的所有数中有多少个数字均不相同的数。
另之为f[n],可得:
f[1] = 10; (0, 1,2,3,4,5,6,7,8,9)
f[2] = 9 × 9; (9 ×9,可以在1 - 9 中选出一个数字为长度为2的数字的第一位,在0 以及 1 - 9 除去被先前选中的数字中选出一个数字为长度为2的数字的第二位)
f[3] = 9 × 9 × 8;
f[4] = 9 × 9 × 8 × 7;
f[5] = 9 × 9 × 8 × 7 × 6;
f[6] = 9 × 9 × 8 × 7 × 6 × 5;
......
f[10] = 9 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1;
f[11] = 0;
f[12] = 0;
所以源程序可以这么写 !
int countNumbersWithUniqueDigits(int n) {
if(n == 0){
return 1;
}else if(n > 10){
return 0;
}
int result = 10;
int uniqueDigits = 9;
int availableNumber = 9;
while(n > 1 && availableNumber > 0){
uniqueDigits *= availableNumber;
res += uniqueDigits;
n -- ;
availableNumber --;
}
return res;
}