统计各位数字都不同的数字个数

给你一个整数 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

思路：

根据排列组合的知识动态规划求解 当n==1时，0~9，答案为res(n=1)=10 当n==2时，首先10以内的0~9还是正常加上，两位数就从十位和个位分析， 十位可以是除0以外的任意一位数(故有9种可能)，当十位数选定以后， 个位数可以是除开与十位数相同的那一位的任意一种数字(所以也是9种) 动态规划这个问题，所以这时候答案 res(n = 2)=res(n=1)+9*9; 当n==3时，同样的道理：百位可以是除0以外的数(9种)， 十位可以是与百位不同的任意一个数(9种)， 个位可以是与百位和十位均不同的一个数(8种)，res(n=3)=res(n=2)+ 9* 9* 8 所以当n继续变大的时候，递归表达式 f(n)=f(n-1)+9* 9* 8* 7* 6*. …后面一共n项

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

时间复杂度： O(n)，循环n次 空间复杂度： 无额外空间消耗，因此空间复杂度为O(1).