1.题目

给定一个按非递减顺序排列的数字数组 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 <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/numbers-at-most-n-given-digit-set
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

（1）数位 dp
思路参考该 LeetCode 用户题解。

3.代码实现（Java）

//思路1————数位 dp
class Solution {
    
    private String[] digits;
    private char[] s;
    private int[] dp;
    
    public int atMostNGivenDigitSet(String[] digits, int n) {
        this.digits = digits;
        this.s = Integer.toString(n).toCharArray();
        this.dp = new int[s.length];
        //初始化 dp
        Arrays.fill(dp, -1);
        return digitDp(0, true, false);
    }
    /*
        (1) i 表示当前遍历到的数字位数
        (2) isLimit 表示当前是否受到了 n 的约束。若为 true，则第 i 位填入的数字至多为 s[i]， 否则至多为 9。
        例如 n = 234，如果前面填了 23，那么最后一位至多填 4；如果前面填的不是 23，那么最后一位至多填 9。
        如果在受到约束的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。
        (3) isNum 表示 i 前面的数位是否填了数字。若为 false，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；
        若为 true，则必须填数字，且要填入的数字从 0 开始。这样我们可以控制构造出的是一位数/两位数/三位数等等。
        对于本题而言，要填入的数字可直接从 digits 中选择。
    */
    private int digitDp(int i, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            //如果填了数字，则视为 1 种合法方案
            return isNum ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i] >= 0) {
            // 在不受到任何约束的情况下，返回记录的结果，避免重复运算
            return dp[i];
        }
        int res = 0;
        if (!isNum) {
            /*
                (1) 前面不填数字，那么可以跳过当前数位，也不填数字
                (2) isLimit 改为 false，由于没有填数字，位数比 n 的要短，所以不会受到 n 的约束
                (3) isNum 仍然为 false，因为没有填任何数字
            */
            res = digitDp(i + 1, false, false);
        }
        //根据是否受到了约束，来决定可以填的数字的上限
        char up = isLimit ? s[i] : '9';
        //枚举要填入的数字
        for (String d : digits) {
            if (d.charAt(0) > up) {
                break;
            }
            res += digitDp(i + 1, isLimit && d.charAt(0) == up, true);
        }
        if (!isLimit && isNum) {
            //在不受到任何约束的情况下，记录结果
            dp[i] = res;
        }
        return res;
    }
}