AI summary
type
status
date
Jan 18, 2024 08:01 AM
slug
summary
tags
category
icon
password
引言
首次接触数位DP的朋友，可以参考以下两手资料：
- 灵神的数位DP V1.0模板：902. 最大为 N 的数字组合 - 力扣（LeetCode）以及V2.0版本 2999. 统计强大整数的数目 - 力扣（LeetCode）
建议先看灵神的视频讲解，wiki作为百科类型细节补充
下文主要在以上资料的基础上，记录个人做数位DP题目的 JavaScript 代码以及个人心得
LeetCode 数位DP 题目列表
1. 模板 V 1.0 → V 2.0
建议练习直接从V 2.0上手，V 1.0 和 V 2.0 的主要区别就是增加了对下界的判断
dLimit （这里注意，下面个人提出的前导零动态计算方式 isPreZero 必须依赖该参数，即 V 1.0模板是不支持的），再根据具体题目要求，自己判断调节 2 个位置：- DP状态空间的第二维：也就是
dp[i][xxx]中的xxx是什么，需要具体问题具体分析，有些题目甚至可以简化不需要第二维度，直接用dp[i]
- 循环
0~9时，根据题目限制进行剪枝 + 第二维状态的更新
Talk is Cheap, Show me the code
下面给出我的 V 2.0 JS 版本
根据上述步骤，套用模板你需要根据题目改动的：
- 根据题目定义 dp (即
memo) 第二维度，本题就是对应数字 0~9 的 digits mask，也就是二进制表示是否选择了某一个数，同时递归 dfs 时，也需要传递第二个参数 mask
- for 循环中，根据题目的限制，修改条件判断，也就是 if 的地方，以及下一轮迭代时，dp 第二维度如何变更
以上，基本可套用绝大部分数位DP题了，灵神YYDS！o(￣▽￣)ｄ
2. 前导零处理
前导零是什么？打比方说题目允许的取数范围是
1~1000 ，那么 34 对应的是 "0034" ，也就是低位数字中左侧补充的 0，以上面模板对应的 1012. 至少有 1 位重复的数字 - 力扣（LeetCode） 题为例，如果不处理前导零，那么在循环这里对于
"0034" ，就会判断有两个重复的 0 而跳出循环，因此需要对该 case 进行识别，也就是我上面写的 isPreZero isPreZero 的计算原理是：- 先计算最小数字
nstr1的前导零有几位，因为本题固定下界是1，上界数字的长度是N，从而得到 ，对应本题就是N-1
- 在
j循环时判断，试想什么情况下会是前导零？一定是循环时前置位和下界一样是0才行，因为如果当前前置位和下界不同，那么要么当前数字不为0，也就不可能是前导零；要么下界不为0，如果下界都不为0了，你取的数是一定比下界大的，也就不可能是前导零的 case，因此判断条件是
3. 题目的一些坑
想着根据以上模板理论，做题应该轻松 easy 了吧？
确实一部分题目直接套上诉公式可简单搞定。但是部分 hard 题，我依然会卡各种 case，原因归结也可以说简单，就是对上述第二维度以及if条件判断的逻辑思考不到位。
下面我会以题目为核心，给出题目的 JavaScript 解法，同时总结一下个人遇到的坑点
902. 最大为 N 的数字组合 - 力扣（LeetCode）
该题类似完全背包，但是你用 的时间复杂度求解会TLE，所以要利用数位的规律，进一步优化
那么该问题的第二维度怎么想？坑就在这里，其实你不需要记录前置状态，因为
i+1...n 位的选取结果不依赖 0...i 的，所以只用一个维度 dp[i] 即可，另外就是剪枝的判断，我是用了 set，你也可以参考灵神的遍历 digits，同时判断值是否大于 up600. 不含连续1的非负整数 - 力扣（LeetCode）
二进制不含连续1，关键在于这里数位dp第一维度，注意是第一维度遍历，不是
十进制 了，而是 二进制 ，然后第二维度就是前一位是否 == 0，就很好解了1012. 至少有 1 位重复的数字 - 力扣（LeetCode）
本题难点在
逆向思维，正向想的话，dp第二维度的状态空间，或者说 mask 很难构建，我尝试了利用 M * log(N) 来表示 0 ~ 9 前面出现的次数，但是中途有很多额外的分支需要判断处理，很恶心但是如果反过来想就很简单了，详细参考本人题解 1012. 至少有 1 位重复的数字 - 力扣（LeetCode），最后答案就是
n - dfs - 作者:Tony
- 链接:https://wangqiwei.life/article/algo-dp-digits
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。