最大為 N 的數字組合

題目

給定一個按 非遞減順序 排列的數字數組 digits 。你可以用任意次數 digits[i] 來寫的數字。例如，如果 digits = ['1','3','5']，我們可以寫數字，如 '13', '551', 和 '1351315'。

傳回 可以生成的小于或等于給定整數 n 的正整數的個數 。

示例 1：

輸入：digits = ["1","3","5","7"], n = 100
輸出：20
解釋：
可寫出的 20 個數字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

輸入：digits = ["1","4","9"], n = 1000000000
輸出：29523
解釋：
我們可以寫 3 個一位數字，9 個兩位數字，27 個三位數字，
81 個四位數字，243 個五位數字，729 個六位數字，
2187 個七位數字，6561 個八位數字和 19683 個九位數字。
總共，可以使用D中的數字寫出 29523 個整數。

示例 3:

輸入：digits = ["7"], n = 8
輸出：1
 

提示：

1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是從 '1' 到 '9' 的數
digits 中的所有值都 不同 
digits 按 非遞減順序 排列
1 <= n <= 109      

題解

數位DP入門題：

題目要求傳回通過digits中的數字可以生成的<=正整數 n 的正整數個數

如：digits=["1","3"] n=52 答案是：1,3,11,13,31,3

将digits轉化為int數組類型的nums

記nums的長度為M，f(x)為nums能組成的位于[1,x]的數字個數，正整數x的長度為N

1. 位數小于N的部分，這部分可通過計算得到，設此時數字的位數為k，那麼這部分個數為 ∑M^k(k∈[1,N-1])（nums數字可以複用）

2. 位數等于N的部分，且最高位比x最高位小，這部分也可通過計算得到，設r為nums在x對應位能取到的數字最大索引

   那麼x對應位可以取到digits[0,r]，後面任意取都不會超過x，是以這部分個數為 (r+1)*M^(N-p)，其中N-p表示目前位後面還有多少位數

3. 位數等于N的部分，且最高位等于x最高位，最高位處保守隻能取到digits[0,r-1]，這部分個數為 r*M^(N-p)

   還沒完，還要累加最高位為digits[r]的情況，這取決于後面數字的貢獻數，參考下一位數屬于哪種情況

   最後答案就是f(n)

/**
 * @param {string[]} digits
 * @param {number} n
 * @return {number}
 */
var atMostNGivenDigitSet = function(digits, n) {
    const s = n + '';
    const K = s.length;
    const dp = new Array(K+1).fill(0);
    dp[K] = 1;

    for(let i = K -1; i >= 0; --i) {
        let si = s[i];
        for(let j=0; j < digits.length; j++) {
            if(digits[j] < si) {
                dp[i] += Math.pow(digits.length, K-i-1)
            } else if(digits[j] == si) {
                dp[i] += dp[i+1];
            }
        }
    }

    for(let k=1; k< K; ++k) {
        dp[0] += Math.pow(digits.length, k)
    }

    return dp[0]
};      

總結