题目描述：

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

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

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

提示：
0 <= n <= 8

解题思路一：递归，因为结果等于countNumbersWithUniqueDigits(n-1)+f(n)，用到了排列组合,例如两位不同的有，第一位先从1-9里选，第二位从0~9里选（和第一位不同）有9*9=81个数。

例如n=2，则计算f（2）+countNumbersWithUniqueDigits（1）=81+f（1）+countNumbersWithUniqueDigits（0）=81+9+1=91

class Solution {
public:
    int f(int n){
        int temp=1;
        for(int i=0;i<n;++i){
            if(i==0) temp*=(9-i);
            else temp*=(10-i);
        }
        return temp;
    }
    int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        else return countNumbersWithUniqueDigits(n-1)+f(n);
    }
};

解题思路二：我朋友想到的递归

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        if(n==1) return 10;
        else return countNumbersWithUniqueDigits(n-1)+(countNumbersWithUniqueDigits(n-1)-countNumbersWithUniqueDigits(n-2))*(11-n);
    }
};

解题思路三：动态规划，记录i位数字中重复数字的个数，最后用10^n减去各位重复数字的总和。

pow功能：计算x的y次幂。

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        vector<int> dp(n+1);
        for(int i = 2; i <= n; ++i)
            dp[i] = dp[i-1]*10 + (9*pow(10, i-2) - dp[i-1])*(i-1);
        int sum = 0;
        for(auto& x : dp)
            sum += x;
        return pow(10, n) - sum;
    }
};