题目

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n 。

示例

示例1：

1
2
3

输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例2：

1 2	输入：n = 0 输出：1

题解

刚看完：好欸又是暴力完活的一天！…… 但是这个难度绝对不会是暴力能够解决的！

仔细思索可以发现，当 n=2 时，我们易得出重复数字是 11、22、33、44……88、99 这几个，那么当 n=3 时呢？会发现这里面包含了 9 个 n=2 的重复数字 x11、x22……x99 ，当然也有诸如 100、101、202…… 这样的数字当然也是。

所以这样子有叠加性质的答案绝对是动态规划无疑了！（动规真乃天杀我也！！！）

所以我们应该开始往动规的方向去思考这道题的转移方程了，但是我不会写x（绝望）。

所以直接一点好了。

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

dp [ i-1 ] 应该是不用解释的；
(10 - i - 1 ) 可以举个栗子：

n=2 时，符合题意的数字共有 91个，剩余的 ~~被选中的孩子~~ 其实是在 n=1 的数字中刚好选择了能让它成为重复数字的非重复数字，像 1 选择了 1 成为了 11，但如果它选择的是除 1 以外的其他 9 个数字就不会叛变了。

n=3 时情况也是一样的，叛变的 n=2 中的某些数字在成为三位数时恰好选择了能让它成为重复数字的数字，像是 13 找了个 1 成为了 113，这样的数字如果选择的是 1 和 3 之外的 8 个数字就不会叛变了。

有没有发现？叛变了的数字是其中占比的 i-1/10 ，而没叛变的数字是其中占比的 1-(i-1/10) 也就是 ( dp[i-1] - dp[i-2] ) * (10 - i - 1 ) 了。
( dp[i-1] - dp[i-2] ) 其实是为了避免重复计算。在上面的例子中，因为位数为 1 的数在 n=2 时就已经被计算了，我们只需要关心位数为 2 的数就可以了。

题解就是这么多了，写代码吧！

代码

// 用时0ms 超越 100% 消耗 5.9MB 超越34.29%
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n==0)
            return 1;
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1]=10;
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1));
        return dp[n];
    }
};