Leetcode解题报告——357. Count Numbers

题目要求：
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

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])

题目大意：
给定非负整数 n ，求 由不同数字组成的数 X ( 0 ≤ X < 10^n ) 的数目

思路分析：
令 F(n)，G(n) 表示 n 中 X 的数目，则：
F (0 ≤ X < 10^n ) = F( 0 ≤ X < 10^n-1) + G ( 10^n-1 ≤ X < 10^n )
G ( 10^n-1 ≤ X < 10^n ) 表示为 位数 为 n 的 X 的数目
这是一个排列组合问题： 9 * 8 * 7 * 6.....
根据上述思路，我们使用动态规划就可以解决这次的问题。

全部代码：

public int countNumbersWithUniqueDigits(int n) {
 //dp[i] 表示的是位数为 i 的 X 的数量，即G（n）
        int [] dp = new int[n+1];
        dp[0] = 1;
        int result = 1;
        for (int i = 1; i <=n ; i++) {
             if(i == 1) dp[i] = 9;
             else dp[i] = dp[i-1]*(11-i);
             result += dp[i];
        }
        return result;
    }