一、题目

二、分析与解答

定义 dp [i] 表示 i 个数字有多少个数字是重复的；
若 i = 2，则表示 10~99 之间有多少个是重复的；若 i =3，表示100 - 999 之间有多少个是重复的。
如何由 dp [i-1] 推到 dp[i] 呢？

• 第一种情况：dp [i] 是重复的，那么后面增加任何数字都是重复元素：dp [i] = 10 * dp[i-1];
• 若前面的元素不重复，则个数为 pow(10,i-1) - pow(10,i-2) = 9 pow(10,i-2) ，9 pow(10,i-2) - dp[i-1] 即为不重复元素的个数。后面再加上 i-1 个即会变成重复的元素。

dp [i] = 10 dp[i-1] + (9 pow(10,i-2) - dp[i-1]) * (i-1);

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n == 0) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 0;
        for(int i = 2;i<=n; i++) {
            dp[i] = 10 * dp[i-1] + (9 * (int)Math.pow(10,i-2) - dp[i-1]) * (i-1);
        }
        int sum = 0;
        for(int d : dp) {
            sum += d;
        }
        return(int)Math.pow(10,n) - sum;
    }
}