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

题目

思路

• 可以粗糙地理解成，位数是n的数字中，有多少个符合条件的。n = 0的时候需要特殊处理一下，其他都是一样的。
• dp[i]表示长度为i的数字，一共有多少个符合条件的。

• ，最终结果就是。

  代码

  class Solution {
  public:
  int countNumbersWithUniqueDigits(int n) {
      // dp[i]表示长度为i的数字有多少种可能
      if (n == 0) {
          return 1;
      }
      if (n == 1) {
          return 10;
      }
      vector<int> dp(n + 1, 0);
      dp[0] = 1, dp[1] = 9; dp[2] = 9 * 9;
      for (int i = 2; i <= n; i++) {
          dp[i] = dp[i - 1] * (10 - (i - 1));
      }
      int res = 0;
      for (int i = 0; i <= n; i++) {
          res += dp[i];
      }
      return res;
  }
  };