LeetCode_动态规划_困难_902.最大为 N 的数字组合

r囧r小猫 2023-10-07 20:26 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 109

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

## 2.思路 ##

（1）数位 dp  
思路参考[该 LeetCode 用户题解][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;
        }
    }

[LeetCode]: https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/solution/shu-wei-dp-tong-yong-mo-ban-xiang-xi-zhu-e5dg/