数位动态规划
数位DP介绍
- 可以解决的问题
对于「数位 DP」题，都存在「询问[a, b]（a 和 b 均为正整数，且 a符合特定条件的数值个数为多少」的一般形式，通常我们需要实现一个查询 [0,x] 有多少合法数值的函数 f(int x)，然后应用「容斥原理」求解出 [a,b] 的个数：f(b)−f(a−1) - 这个区间可能很大，暴力代码一般会超时，此时就可以使用数位DP解决该类问题。
- 由于数位是按位dp，数的大小对复杂度的影响很小，时间复杂度为状态个数 * 单个状态的转移次数
- 模板题
试计算在区间 1到 n的所有整数中，数字 x（0≤x≤9）共出现了多少次？例如，在 1 到 11 中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1出现了 4次。
模板
作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-digit-one/solutions/1750339/by-endlesscheng-h9ua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
相关题目
1.数字1的个数【LC233】
2022/11/25
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
实现
- 首先将n转化为字符串数组
s，存储高位至低位的数值大小，会影响isLimit - 然后使用dp数组记录在不受到约束时，第i位枚举值固定时的合法方案数，即从左往右第i位之后所有枚举数中1的个数【不包括第i位】
- 然后通过for循环，枚举每一位其所有可能的值
- 举例说明：计算所有小于等于
n的非负整数中数字1出现的个数。
如果当前的枚举数不受限，并且状态dp[i,cnt1]之前已经计算过，那么此时第i位枚举值固定时的合法方案数不需要重新计算，直接返回dp[i,cnt1]即可
class Solution { char s[]; int dp[][]; public int countDigitOne(int n) { s = Integer.toString(n).toCharArray(); int m = s.length; dp = new int[m][m]; for (int i = 0; i < m; i++) Arrays.fill(dp[i], -1); return f(0, 0, true);// 第i位受isLimit约束 } int f(int i, int cnt1, boolean isLimit) { if (i == s.length) return cnt1; if (!isLimit && dp[i][cnt1] >= 0) return dp[i][cnt1]; int res = 0; // 记录从左往右第i+1位之后所有枚举数中1的个数 for (int d = 0, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) // d代表枚举要填入的数字 up代表上限值 不受限则为9 受限则为第i位的值 // 以下代码运用到了回溯 // 具体含义为：寻找从左往右第i+1为以及之后数位中1的个数，因此需要更新cnt1以及isLimit // cnt1含义为前面i位填充1的个数，因此如果当前位填入的数字为i，那么cnt1 + 1,否则加0 // isLimit含义为该位填充数字是否受限，取决于前一次填充是否受限，以及当前填充是否达到up res += f(i + 1, cnt1 + (d == 1 ? 1 : 0), isLimit && d == up); if (!isLimit) dp[i][cnt1] = res;// dp数组的含义为在不受到约束时第i位的合法方案数，即从左往右第i位之后所有枚举数中1的个数【不包括第i位】 return res; } }
复杂度
- 时间复杂度：O(logn)，$\lceil log_{10}n \rceil+1$为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即O(logn)，而单个状态的转移次数 = O(2) = O(1)，所以时间复杂度为O(logn)
- 空间复杂度：O(logn)
2.不含连续1的非负整数【LC600】
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
2022/11/25
同LC233的思路相同，区别在于把数使用二进制表示
- 思路：数位dp
首先将n转换成二进制int数组binary，定义f(i,pre,isLimit,isNum)表示构造从左往右第i位及其之后数位的合法方案数，即不存在连续1的个数，其余参数的含义为：
实现
- 首先将n转化为二进制形式，并使用int数组
binary存储 - 然后使用dp[i][j]数组代表在不受到约束时，第i位枚举值固定为j时的，合法方案数，即从左往右第i位之后所有枚举数中不含1的个数【不包括第i位】
- 然后对于每一位枚举其所有可能的值，由于枚举值只可能为0或者1，因此可以不使用for循环，直接判定
- 如果不受限并且前一位不为1并且最大值为0，那么第i位可以填充1
- 任何情况均可以填充0
- 代码
class Solution { int [] binary; int[][] dp; public int findIntegers(int n) { int m = 32; binary = new int[m];// 转化为二进制数组 for (int i = 0; i < m; i++){ binary[i] = (n >> (31-i)) & 1; } dp = new int[m][2]; for (int i = 0; i < m; i++){ Arrays.fill(dp[i],-1); } int i = 0; while (i < m && binary[i] == 0){// 找到第一个不为0的二进制 i++; } return f(i,0,true); } public int f(int i, int pre, boolean isLimit){ if (i == binary.length){ return 1; } if (!isLimit && dp[i][pre] >= 0){// 不受限 并以及计算过 return dp[i][pre]; } int res = 0;// 记录第i位之后的枚举可能性 int up = isLimit ? binary[i] : 1;// res += f(i + 1, 0, isLimit && up == 0);// 第i+1位填0 if (pre != 1 && up == 1){ res += f(i + 1, 1, isLimit);// 第i位填1 } if (!isLimit){ dp[i][pre] = res; } return res; } }
【题型总结】数位dp（二）：https://developer.aliyun.com/article/1405899?spm=a2c6h.13148508.setting.14.45fd4f0eFyVSCn
