357. 統(tǒng)計各位數(shù)字都不同的數(shù)字個數(shù)

357. 統(tǒng)計各位數(shù)字都不同的數(shù)字個數(shù)

給你一個整數(shù)?n?，統(tǒng)計并返回各位數(shù)字都不同的數(shù)字?x?的個數(shù)，其中?0 <= x < 10n?。

示例 1：

輸入：n = 2輸出：91解釋：答案應為除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范圍內(nèi)的所有數(shù)字。

示例 2：

輸入：n = 0輸出：1

?

看到了想用全排列試試看的，果斷超時……

看了看題解，用的dp，大佬們真的太強了

class?Solution:

????def?countNumbersWithUniqueDigits(self,?n:?int)?->?int:

????????dp=[0]*10

????????dp[0]=1

????????dp[1]=10

????????for?i?in?range(2,10):

????????????dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1))

????????return?dp[n]

題解在這里：

n=0，數(shù)字有{0}1個。

n=1，數(shù)字有{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}10個。

n=2，數(shù)字包括兩部分之和，一部分為n=1的所有10個答案，另一部分為長度為2的新增數(shù)字。長度為2的新增數(shù)字可以在n=1的所有9個數(shù)字基礎上進行拼接（0不能算）。例如：

從n=1的數(shù)字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中隨便取出一個除0以外的數(shù)字（因為0不能作為起始數(shù)字！），我們?nèi)?好了。通過在2的尾巴處拼接一位數(shù)字可以得到新的合法數(shù)字有：

{20， 21，23，24，25，26，27，28，29}，

可以看到，除了不能在尾巴處拼接一個2（兩個連續(xù)的2就非法了?。?，0-9種一共有9個數(shù)字可以拿來拼接在尾巴處。新增答案為9個。同理，對于n=1數(shù)字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中的其他任意非0數(shù)也可以進行拼接操作，一共可以新增9*9個答案。

最終，n=2的合法數(shù)字，n=1時的答案 + 長度為2的數(shù)字個數(shù)（9*9個）= 10 + 81 = 91。

n=3時同理，只不過此時可以用拼接的數(shù)字減少為了8個，此時答案為10 + 9 * 9 + 9 * 9 * 8 = 739。

n=4時同理，只不過此時可以用拼接的數(shù)字減少為了7個，此時答案為10 + 9 * 9 + 9 * 9 * 8 + 9 * 9 * 8 * 7 = 5275。

通過歸納不難得到，假設 dp[i] 即 n = i時的答案，則動態(tài)轉移方程為：

dp[i] = dp[i-1] + (dp[i-1] - dp[i-2])*(10-(i-1))

轉移的初始條件為

dp[0] = 1

dp[1] = 10