计算给定范围内具有唯一数字的所有数字

这是一道面试题。计算 [1, N] 范围内具有唯一数字（十进制）的所有数字。

显而易见的解决方案是测试范围内的每个数字是否唯一。我们还可以生成具有唯一数字的所有数字（作为排列）并测试它们是否在范围内。

现在我想知道这个问题是否有DP（动态规划）解决方案。

我在想：

Number of unique digits numbers 1-5324
=   Number of unique digits numbers 1-9
  + Number of unique digits numbers 10-99
  + Number of unique digits numbers 100-999
  + Number of unique digits numbers 1000-5324

So:

f(n) = Number of unique digits numbers with length n.
f(1) = 9 (1-9)
f(2) = 9*9 (1-9 * 0-9 (excluding first digit))
f(3) = 9*9*8 (1-9 * 0-9 (excluding first digit) * 0-9 (excluding first 2 digits))
f(4) = 9*9*8*7

将以上所有内容相加，直到 N 的位数为负 1。

那么你只需要做Number of unique digits numbers 1000-5324

And:

Number of unique digits numbers 1000-5324
=   Number of unique digits numbers 1000-4999
  + Number of unique digits numbers 5000-5299
  + Number of unique digits numbers 5300-5319
  + Number of unique digits numbers 5320-5324

So:

N = 5324

If N[0] = 1, there are 9*8*7 possibilities for the other digits
If N[0] = 2, there are 9*8*7 possibilities for the other digits
If N[0] = 3, there are 9*8*7 possibilities for the other digits
If N[0] = 4, there are 9*8*7 possibilities for the other digits
If N[0] = 5
  If N[1] = 0, there are 8*7 possibilities for the other digits
  If N[1] = 1, there are 8*7 possibilities for the other digits
  If N[1] = 2, there are 8*7 possibilities for the other digits
  If N[1] = 3
    If N[2] = 0, there are 7 possibilities for the other digits
    If N[2] = 1, there are 7 possibilities for the other digits
    If N[2] = 2
      If N[3] = 0, there is 1 possibility (no other digits)
      If N[3] = 1, there is 1 possibility (no other digits)
      If N[3] = 2, there is 1 possibility (no other digits)
      If N[3] = 3, there is 1 possibility (no other digits)

上面的内容是这样的：

uniques += (N[0]-1)*9!/(9-N.length+1)!
for (int i = 1:N.length)
  uniques += N[i]*(9-i)!/(9-N.length+1)!

// don't forget N
if (hasUniqueDigits(N))
  uniques += 1

你真的不需要 DP，因为上面的应该足够快了。

EDIT:

上面实际上需要更复杂一点（上面的 N[2] = 2 和 N[3] = 2 是无效的）。它需要更像：

binary used[10]
uniques += (N[0]-1)*9!/(9-N.length+1)!
used[N[0]] = 1
for (int i = 1:N.length)
  uniques += (N[i]-sum(used 0 to N[i]))*(9-i)!/(9-N.length+1)!
  if (used[N[i]] == 1)
    break
  used[N[i]] = 1

// still need to remember N
if (hasUniqueDigits(N))
  uniques += 1