# 357 Count Numbers with Unique Digits

給一正整數n，回傳0 < x < 10^n的範圍內，有幾個數字每一位數都不相同

Concept 先觀察一下

f(0) = 1
f(1) = 10
f(2) = 91

f(2)的範圍包括了從0到100，其中0~10在f(1)已經算過了不用重算，所以只要算11~100的部分。11~100可以說是1,2,3,4,5,6,7,8,9後面再加一位， 總共會有9*9種可能。

可以歸納成以下規則 f(i) = f(i-1) + (f(i-1)-f(i-2)) * (10-i+1)

Code

public int countNumbersWithUniqueDigits(int n) {

    if(n == 0) return 1;    
    int[] counts = new int[n+1];    
    counts[0] = 1;
    counts[1] = 10;

    for(int i = 2; i < n + 1; i++)
        counts[i] = counts[i-1] + (counts[i-1] - counts[i-2]) * (10 - i + 1);

    return counts[n];
}

ref: https://leetcode.com/problems/count-numbers-with-unique-digits/discuss/145868/Java-DP-Solution-with-O(n)-time-complexity