357. Count Numbers with Unique Digits

一、解题思路

  这道题是一道正儿八经的数学题，1位数不存在重复数字的情况：

  dp[1] = 10

  2位数不出现重复数字的问题实际上就是求解：10个数字中取2个数字的排列问题，因为0不能作为首位，需要减去9种0为首部的情况，即

  10! / 8! - 9 = 9 * 9

  那么3位数不存在重复数字的情况为：

  10! / 7! - 8 * 9 = 9 * 9 * 8

  最后得出通项公式：

  dp[k] = 9 * 9 * .... * (9 - k + 2) 

  最终代码如下：

二、代码实现

const countNumbersWithUniqueDigits = n => {
  if (n == 0) {
    return 1
  }
  let ans = 10, base = 9
  for (let i = 2; i <= Math.min(10, n); i++) {
    base = base * (9 - i + 2)
    ans += base
  }
  return ans
}