1.对于此题,如果n大于10则没有任何意义,因为一个十位数必定有重复的位数 2.如果n等于1的话,它只用考虑个位,所以有十种情况 3.如果n等于2的话要考虑情况 只有个位数字:10种情况 个位十位数字都有:十位可能取值有9种,个位取值为了不同也有9种 所以一共就是10+81=91中 4.可以看出来如果考虑n,要考虑n位数,(n-1)，(n-2)…位数的情况 所以可以使用动态规划 要求n只需要知道n-1时候有多少情况和n位数的时候有多少情况. 5. 当n等于i的时候,求的就是i位数的时候,有多少种情况 :最高位有9种,再次一位有9种,接着有8种… public int countNumbersWithUniqueDigits(int n){ //如果n大于10则没意义,必定有重复的数字, //如果n为1则有10种情况, //如果n为2,按照两位数来计算:因为首位不能为0,所以十位只有9种情况,所以个位也只有9种情况, // 按照一位数来计算:有10种情况, //所以n的总和就为 (n-1)时候的情况+第n位的情况*第n-1位的情况
//1.大于10直接返回-1 if(n > 10){ return -1; } //2.n为1有10种情况 int[] dp = new int[n+1]; dp[0] = 1; //3.动态规划求其他n的情况 for(int i = 1;i <= n;i++){ dp[i] = dp[i-1]+count(i); } return dp[n]; } /** * 当n等于2的时候,求的就是两位数的时候,有多少种情况 :十位有9种,个位有9种 * 当n等于i的时候,求的就是i位数的时候,有多少种情况 :最高位有9种,再次一位有9种,接着有8种.... * @param i * @return */ private int count(Integer i){ int result = 9; //代表最高位 int num = 9; //代表下一位有多少种情况 while(--i > 0){ result *= num; num--; } return result; }