【题型总结】数位dp（二）

【题型总结】数位dp（一）：https://developer.aliyun.com/article/1405889?spm=a2c6h.13148508.setting.28.45fd4f0eBwyRJL

4.至少有1位重复的数字【LC1012】

Given an integer n, return the number of positive integers in the range[1, n] that have at least one repeated digit.

2022/11/28

• 思路：将题目转化为[1,n]范围内所有数的个数减去各位数字都不同的数字个数，因此可采用同统计各位数字都不同的数字个数【LC357】相同的数位dp思路，只需将最低位的枚举数值改为从1开始即可
  
• 代码
  

class Solution {
    char s[];
    int dp[][];
    public int numDupDigitsAtMostN(int n) {
        s = Integer.toString(n).toCharArray();
        var m = s.length;
        dp = new int[m][1 << 10];
        for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1);
        return n - f(0, 0, true, false);
    }
    // 最小值为1
    int f(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == s.length) return isNum ? 1 : 0;// 前一位为数字才有合法数字
        if (!isLimit && isNum && dp[i][mask] >= 0) return dp[i][mask];
        var res = 0;
        if (!isNum) res = f(i + 1, mask, false, false); // 前一位不是数字 那么可以跳过当前数位
        // 前一位为数字，那么第i位可以从0开始枚举；否则，均从1开始枚举【与LC357的区别，合法数的范围为[1,n]】
        for (int d = isNum ? 0 : 1, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
            if ((mask >> d & 1) == 0) // d 不在 mask 中
                // mask | (1 << d) 将mask的第d位赋值为1
                res += f(i + 1, mask | (1 << d), isLimit && d == up, true);
        if (!isLimit && isNum) dp[i][mask] = res;
        return res;
    }
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/numbers-with-repeated-digits/solutions/1748539/by-endlesscheng-c5vg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

• 时间复杂度：O(logn)，n为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即O(logn)，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为O(logn)
• 空间复杂度：O(logn)

5.最大为N的数字组合【LC902】

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

2022/11/29 终于自己做出来了！！！！！

• 思路：数位dp，与其他题目不同的是，每位的数字只能在数组digits内选，因此使用mask记录digits内的数字，并用位运算判断当前数字是否可以使用
  

首先将n转换成字符串s，定义f(i,mask,isLimit,isNum)表示构造从左往右第i位及其之后数位的合法方案数，即各位数字都不同的数字个数，其余参数的含义为：

实现

• 首先将字符串n对应的数值存入字符数组s，存储高位至低位的数值大小，会影响isLimit【本题需要判断的数值范围为**[1,n]**】
• 然后使用dp数组记录在不受到约束时，第i位枚举范围固定时的合法方案数，即从左往右第i位之后所有数字个数【不包括第i位】【由于mask为固定值，因此dp为一维数组即可存储】
• 如果不受限并且前一位是数值，那么可以查询是否已经计算过第i位枚举范围一定时的合法方案数，若dp[i] >= 0，则表示已经计算过，可直接返回
• 否则枚举第i位的可能性【既可以填入数字，也可以不填入数字】
• 不填入数字：如果isNum为false，那么第i位也可以不填入数字此时对结果的贡献为f(i+1,mask,false,false)
  

• 填入数字：通过for循环，枚举每一位其所有可能的值d

1. 初始值：可能为0或者1

• isNum为true即前一位为数字时，那么第i位可以从0开始枚举
• 否则，均从1开始枚举

2. 上限值：由limit决定

• 如果受限，那么枚举的最大值为s[i]

3. 只有d在mask中时，才对结果有贡献，共享为f(i+1,mask,isLimit && d==up,true)

• 如果不受限并且前一位为数值，那么记录result至dp数组中
• 代码

class Solution {
    char[] s;
    int[] dp;
    public int atMostNGivenDigitSet(String[] digits, int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        dp = new int[m + 1];
        Arrays.fill(dp, -1);
        int mask = 0;
        for (int i = 0; i < digits.length; i++){
            int d = digits[i].toCharArray()[0] - '0';
            mask |= 1 << d;
        }
        return f(0,mask,true,false);
    }
    public int f(int i, int mask, boolean isLimit,boolean isNum){
        if (i == s.length) return isNum ? 1 : 0;
        if (!isLimit && isNum && dp[i] >= 0) return dp[i];
        int res = 0;
        if (!isNum){
            res += f(i + 1, mask, false, false);
        }
        for (int d = isNum ? 0 : 1, up = isLimit ? s[i] - '0' : 9; d <= up; d++){
            if ((mask >> d & 1) == 1){// d在mask中
                res += f(i + 1, mask, isLimit && d == up, true);
            }
        }
        if (!isLimit && isNum){
            dp[i] = res;
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(logn)，⌈log10n⌉+1\lceil log_{10}n \rceil+1 为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是dp数组的长度，即O(logn)，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为O(logn)
• 空间复杂度：O(logn)，即为动态规划中存储状态需要使用的空间。

6.旋转数字【LC788】

An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. For example:

• 0, 1, and 8 rotate to themselves,
• 2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
• 6 and 9 rotate to each other, and
• the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

数位dp

2022/11/29 终于自己做出来了！！！！！

• 思路：数位dp，与LC902有点相似，但略复杂点，每位的数字只能在⌈可旋转的数字⌋rotate=0,1,2,5,6,8,9内选，并且只有当某一位数字包含数字good=2,5,6,9任意一个时，该数字才是⌈好数：经过旋转后与原数不相等⌋

首先将n转换成字符串s，定义f(i,isGood,isLimit,isNum)表示构造从左往右第i位及其之后数位的合法方案数，即各位数字都不同的数字个数，其余参数的含义为：

• i表示当前构造至从左往右第i位
• isGood 表示前i位数位是否为好数，只要前i位数字包含数组good=2,5,6,9中一个以上数字即为好数。使用int变量表示，不是好数时为0，是好数时为1。
• 由于数字可以重复选取，因此前i位包含几个好数，不会影响后i位的合法方案数，因此只需要记录包含或者不包含即可
• isLimit 表示当前是否受到了n的约束。若为真，则第i位填入的数字至多为s[i]，否则可以枚举至 9。如果在受到约束的情况下填了s[i]，那么后续填入的数字仍会受到n的约束。
• 取决于第i−1位填充是否受限，以及当前填充的数是否达到上限值
• isNum表示i前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为1；若为真，则要填入的数字可以从0开始。
• 在本题中，有无前导0均不影响结果的，因此本题可以不需要参数isNum

在本题中需要记录的状态是dp[i][isGood]，f(0,0,true,false)即为最终结果

• 实现

• 首先将字符串n对应的数值存入字符数组s，存储高位至低位的数值大小，会影响isLimit【本题需要判断的数值范围为**[1,n]**】
• 然后使用dp数组记录在不受到约束时，第i位枚举值固定时的合法方案数，即从左往右第i位之后所有数字个数【不包括第i位】【由于isGood只有两种值，因此使用二维数组存储】
• 如果不受限，那么可以查询是否已经计算过第i位枚举范围一定时的合法方案数，若dp[i][isGood] >= 0，则表示已经计算过，可直接返回
• 否则枚举第i位的可能性
• 通过for循环，枚举每一位其所有可能的值d

1. 初始值：从0开始枚举
2. 上限值：由limit决定

• 如果受限，那么枚举的最大值为s[i]-'0'

3. 只有d在0,1,2,5,6,8,9中时，才对结果有贡献，贡献为f(i+1,isGood,isLimit && d==up)

• 若存在2,5,6,9，那么isGood为1
• 不存在2,5,6,9，那么isGood为0
• 如果不受限，那么记录result至dp数组中
  

• 代码
  

class Solution {
    char[] s;
    int[][] dp;
    public int rotatedDigits(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        dp = new int[m][2];
        for (int i = 0; i < dp.length; i++){
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }
    public int f(int i, int isGood, boolean isLimit,boolean isNum){
        if (i == s.length) return isGood == 1 && isNum ? 1 : 0;
        if (!isLimit && isNum && dp[i][isGood] > -1) return dp[i][isGood];
        int res = 0;
        if (!isNum){`
            res += f(i + 1, isGood, false, false);
        }
        int up = isLimit ? s[i] -'0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++){
            if (d == 0 || d == 1 || d == 8){
                res += f(i + 1, isGood, isLimit && d == up, true);
            }else if (d == 2 || d == 5 || d == 6 || d == 9){
                res += f(i + 1, 1, isLimit && d == up, true);
            }
        }
        if (!isLimit && isNum) dp[i][isGood] = res;
        return res;
    }
}

复杂度

• 时间复杂度：O(logn)，⌈log10n⌉+1\lceil log_{10}n \rceil+1 为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是dp数组的长度，即O(logn)，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为O(logn)
• 空间复杂度：O(logn)，即为动态规划中存储状态需要使用的空间。