02.7.2.4 数位 DP 与其他
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP
02.7.2.4-001 数位 DP 解决什么问题?
一句话结论
数位 DP 统计区间 [0,n] 内满足数位约束(不含某数字、数位和、递增、相邻关系等)的整数个数;按十进制位从高到低 DP,状态记录位置、约束标记与已选特征;区间答案用前缀差分 F(n)-F(l-1)。
概念解释
- 数位:逐位取值。
- 前缀计数:[0,n] 满足条件数。
原理流程
- 实现 F(x) 统计 0~x 合法数。
- 数位 DP 逐位填。
- 区间 = F(r)-F(l-1)。
代码 / 示例
count(l, r) = F(r) - F(l - 1)
常见误区
- 误区:枚举所有数字;正解:数位 DP 按位组合,不遍历整数。
- 误区:区间直接统计;正解:前缀差分。
追问
- Q:数位 DP 适用规模? A:n 可达 10¹⁸ 仍按位数处理。
- Q:统计什么为主? A:个数/合法数值计数。
02.7.2.4-002 数位 DP 状态包含哪些维度?
一句话结论
常见状态:当前位置 pos、是否仍受上界约束 tight、前导零标记 leading、以及题目要求的已选特征(数位和、上一位数字、是否出现某数);维度按约束增减。
概念解释
- tight:前缀是否与上界相同。
- leading:是否仍是前导零。
- 特征:题目累计量。
原理流程
- 列数位约束。
- 确定需要记录的特征。
- 组成 memo 键。
代码 / 示例
dfs(pos, tight, leading, sum)
常见误区
- 误区:漏掉 tight;正解:上界约束决定当前位可取范围。
- 误区:前导零计入数位和;正解:前导零不应参与特征统计。
追问
- Q:状态能重复用吗? A:memo 缓存非 tight 分支,tight 受具体数影响一般不缓存。
- Q:特征维度怎么选? A:只留影响后续判断的量。
02.7.2.4-003 记忆化搜索怎么写数位 DP?
一句话结论
把数字转成数位数组;递归 dfs(pos, tight, leading, 特征),当前位上限由 tight 决定;枚举 0~上限,更新 tight/leading/特征后递归累加;memo 缓存非紧约束状态。
概念解释
- 自顶向下逐位。
- memo 缓存状态。
原理流程
- 转数位。
- 到末位按特征返回 1/0。
- 枚举当前位累加递归。
代码 / 示例
int dfs(int pos, boolean tight, boolean leading, int sum) {
if (pos == digits.length) return leading ? 0 : 1;
if (!tight && memo[pos][leading?1:0][sum] != -1) return ...;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
boolean nextTight = tight && d == limit;
boolean nextLeading = leading && d == 0;
// 累加 dfs(...)
}
}
常见误区
- 误区:tight 状态也缓存;正解:紧约束随上界变化,通常只缓存非 tight。
- 误区:末位前导零返回 1;正解:全零按题意不计入。
追问
- Q:memo 键怎么编码? A:pos、leading、特征压成数组下标。
- Q:复杂度? A:O(位数 × 状态特征 × 10)。
02.7.2.4-004 不含连续 1 的数字(LC 600 类)怎么做?
一句话结论
状态加上一位是否为 1(或上一位数字);当前位取 1 时要求上一位不是 1;逐位枚举累加;统计 [0,n] 内二进制/十进制满足条件的数;memo 记录位置、上一位、tight。
概念解释
- 相邻约束:上一位特征。
- 状态:上一位取值。
原理流程
- 记录上一位。
- 当前位按约束枚举。
- 累加合法分支。
代码 / 示例
选 1 的前提:prev != 1
常见误区
- 误区:只看当前位;正解:相邻约束需记上一位。
- 误区:二进制与十进制口径混淆;正解:按题目进制枚举。
追问
- Q:memo 维度? A:pos × prev × tight。
- Q:复杂度? A:O(位数 × 10 × 10) 量级。
02.7.2.4-005 各位数字之和为 target 怎么计数?
一句话结论
状态记录当前数位和 sum;枚举当前位 d,新和 sum+d;末位判断 sum==target 计数;tight 与 leading 照常处理;数位和作为 memo 维度。
概念解释
- 累计特征:数位和。
- 末位判定。
原理流程
- 状态带 sum。
- 逐位累加 d。
- 末位比对 target。
代码 / 示例
if (pos == len) return sum == target ? 1 : 0;
常见误区
- 误区:前导零也加进 sum;正解:leading 时不计。
- 误区:sum 超 target 不剪枝;正解:可提前返回减少分支。
追问
- Q:数位和上限? A:位数 ×9,memo 数组按此开。
- Q:区间计数? A:F(r)-F(l-1)。
02.7.2.4-006 区间 [0,n] 统计与前缀差分怎么用?
一句话结论
先写 F(x) 统计 0~x 合法个数;任意 [l,r] 答案 F(r)-F(l-1);数位 DP 天然按上界统计,差分避免分别处理左右边界。
概念解释
- 前缀函数。
- 差分相减。
原理流程
- 实现 F(x)。
- 右前缀减左前缀。
- 处理 l=0 边界。
代码 / 示例
int count(int l, int r) { return f(r) - f(l - 1); }
常见误区
- 误区:F(-1) 未定义;正解:l=1 时 f(0) 单独处理。
- 误区:上下界分别 DP;正解:复用 F(x)。
追问
- Q:F(x) 含 0 吗? A:按题意,注意全零是否计入。
- Q:负数区间? A:按题意排除或转换。
02.7.2.4-007 数位 DP 与普通组合计数区别?
一句话结论
数位 DP 按位受上界 tight 约束,逐位枚举并维护特征;普通组合计数在无界集合上用排列组合公式;当上界有限且带数位约束时,数位 DP 逐位处理更直接。
概念解释
- 上界约束。
- 逐位特征。
原理流程
- 判断是否有数值上界。
- 有界数位约束用数位 DP。
- 无界用组合公式。
代码 / 图示
≤n 的合法数 → 数位 DP;不限上界 → 组合计数
常见误区
- 误区:用组合公式处理 tight;正解:上界截断需逐位判断。
- 误区:数位 DP 统计连续值;正解:统计满足数位特征的个数。
追问
- Q:数位 DP 能求最大合法数吗? A:可按位贪心构造,不只是计数。
- Q:进制可变吗? A:可转任意进制数位。
02.7.2.4-008 前导零怎么处理?
一句话结论
leading 标记当前是否仍全为前导零;前导零不参与数位和、相邻特征等统计;遇到首个非零数字关闭 leading;全零数按题意决定是否计入。
概念解释
- 前导零:高位补零。
- 首非零:特征开始计数。
原理流程
- 初始 leading=true。
- 当前位 0 且 leading 保持。
- 非零关闭标记。
代码 / 示例
boolean nextLeading = leading && d == 0;
常见误区
- 误区:前导零当普通数字计入;正解:特征统计从首非零起。
- 误区:相邻特征被前导零干扰;正解:leading 时跳过特征比较。
追问
- Q:全零算合法吗? A:按题意,数字 0 特殊判断。
- Q:leading 进 memo 吗? A:进,影响特征口径。
02.7.2.4-009 tight 上界约束怎么维护?
一句话结论
tight=true 表示前缀与上界完全相同,当前位上限为上界对应位;tight=false 前缀已更小,当前位可取 0~9;新 tight = 旧 tight 且当前位等于上界位。
概念解释
- 紧约束:前缀相同。
- 松弛:前缀已小。
原理流程
- 初始 tight=true。
- 按 tight 定当前位上限。
- 更新下一代 tight。
代码 / 示例
int limit = tight ? digits[pos] : 9;
boolean nextTight = tight && (d == digits[pos]);
常见误区
- 误区:tight 恒 true;正解:选更小的位后松弛。
- 误区:新 tight 判断方向反;正解:必须旧 tight 且同位相等。
追问
- Q:tight 状态为什么少缓存? A:它绑定具体上界,跨数不可复用。
- Q:上限数位不足长度? A:前补零处理。
02.7.2.4-010 数位 DP 初始化与缓存怎么设?
一句话结论
memo 按 pos、leading、特征维度初始 -1;递归末位返回特征是否满足;非 tight 状态才回填缓存;每换一个上界 x 需重置 memo,因为 tight 与数位绑定。
概念解释
- 缓存键。
- 按上界重置。
原理流程
- 开 memo 表。
- 命中非 tight 返回。
- 计算后回填。
代码 / 示例
// f(x) 内部新建 memo,避免跨上界复用
常见误区
- 误区:多组查询共用 memo 不清;正解:上界不同需重置。
- 误区:memo 哨兵与合法计数冲突;正解:用 -1 标记未算。
追问
- Q:末位返回值口径? A:满足特征 1,否则 0。
- Q:缓存维度漏 leading 会怎样? A:前导零口径错乱。
02.7.2.4-011 博弈 DP(Nim 概念)怎么看必胜必败态?
一句话结论
博弈中状态分必胜态(存在一步走到必败态)与必败态(所有走向都是必胜态);终点必败;DP/递推按状态转移标记;Nim 用异或和判断,属于博弈结论而非枚举 DP。
概念解释
- 必胜态:有合法步到必败。
- 必败态:任意步到必胜。
原理流程
- 标记终点必败。
- 枚举可行步。
- 按定义判胜负态。
代码 / 示例
win(s) = 存在 t ∈ next(s) 使 !win(t)
常见误区
- 误区:必胜态定义反;正解:能走到必败才必胜。
- 误区:把平局当必败;正解:无平局规则下才二分胜负。
追问
- Q:Nim 结论是什么? A:异或和非零先手必胜。
- Q:博弈 DP 状态空间大吗? A:组合状态可能指数,需数学结论。
02.7.2.4-012 概率 DP 状态怎么定义?
一句话结论
概率 DP 状态存到达某情形的概率;转移按概率加权累加;初始状态概率 1,其余 0;末态取目标概率;常见于路径概率、抽奖、随机过程题。
概念解释
- 概率值。
- 加权转移。
原理流程
- 定义情形概率。
- 按分支概率累加。
- 取目标状态。
代码 / 示例
dp[next] += dp[cur] * p;
常见误区
- 误区:概率取最大;正解:概率是求和加权。
- 误区:分支概率和不为 1;正解:核对题目概率口径。
追问
- Q:概率 DP 与最值 DP 区别? A:累加 vs 取极值。
- Q:精度问题? A:浮点累计注意误差。
02.7.2.4-013 期望 DP 怎么转移?
一句话结论
期望线性性:E[cur] = Σ p·(代价 + E[next]);状态存期望代价/收益;转移按分支概率加权平均;期望可自底向上或记忆化求解。
概念解释
- 期望:概率加权平均。
- 线性性:可分层累加。
原理流程
- 定义状态期望。
- 枚举分支概率与代价。
- 加权求和。
代码 / 示例
E[cur] = Σ p_i * (cost_i + E[next_i])
常见误区
- 误区:期望取最大分支;正解:按概率平均。
- 误区:循环转移无解;正解:有环期望需解方程,非简单填表。
追问
- Q:期望能叠加吗? A:期望线性性支持分项累加。
- Q:状态有环怎么办? A:列方程求解,记忆化需无环。
02.7.2.4-014 概率状态转移要注意什么?
一句话结论
确认分支互斥且概率和为 1;浮点精度与累计顺序;不可达状态概率 0;多步过程按层/状态递推;概率 DP 不丢弃任何合法分支。
概念解释
- 概率完备。
- 浮点口径。
原理流程
- 核对分支概率。
- 初始化初态。
- 逐层加权更新。
代码 / 示例
p1 + p2 = 1;dp 按转移加权
常见误区
- 误区:概率当计数累加;正解:乘分支概率。
- 误区:浮点直接判等;正解:按容差比较。
追问
- Q:概率 DP 复杂度? A:状态数 × 分支数。
- Q:多源初态怎么设? A:各初态概率按题意分配。
02.7.2.4-015 博弈必胜态/必败态怎么推?
一句话结论
终点无步可走为必败;当前态若有一步进入必败态则必胜;若所有步都进入必胜态则必败;按状态逆序/记忆化标记;两类状态互斥穷尽。
概念解释
- 终态:必败。
- 递推规则。
原理流程
- 标终态必败。
- 反向推必胜/必败。
- 目标状态判定。
代码 / 示例
boolean win(s) {
for (t : next(s)) if (!win(t)) return true;
return false;
}
常见误区
- 误区:一步到必胜也算赢;正解:必须走到必败。
- 误区:状态有环未处理;正解:无环 DAG 才能直接递推。
追问
- Q:石子游戏类结论? A:奇偶/异或等数学结论可直接判。
- Q:平局状态? A:有平局需第三类标记。
02.7.2.4-016 区间博弈与树形博弈怎么结合 DP?
一句话结论
区间博弈在 [i,j] 上记当前玩家相对优势(见 02.7.2.1-009);树形博弈在节点上记胜负/最优选择;二者都是把博弈状态挂到结构上,按子结构合并胜负值。
概念解释
- 结构状态:区间/节点。
- 零和合并。
原理流程
- 状态挂结构单元。
- 子结构胜负上交。
- 当前态按规则判定。
代码 / 示例
区间:dp[i][j] 相对优势;树形:节点选/不选胜负
常见误区
- 误区:博弈只看当前步;正解:需子结构结果支撑。
- 误区:相对优势方向取反错误;正解:后手视角取反。
追问
- Q:博弈 DP 与普通最值 DP 区别? A:对手最优对抗,转移含取反。
- Q:常见结构? A:区间、树、 Nim 堆。
02.7.2.4-017 DP 中 INF 怎么选取?
一句话结论
最值不可达状态用足够小的 -INF(最大值用 INF),绝对值大于任何合法结果且相加不溢出;计数不可达为 0;初始化后转移跳过不可达;注意负价值场景。
概念解释
- 哨兵:不可达。
- 不溢出。
原理流程
- 估合法结果范围。
- 选哨兵绝对值足够大。
- 转移避免哨兵参与非法合并。
代码 / 示例
final int INF = 1_000_000_000;
Arrays.fill(dp, -INF);
常见误区
- 误区:INF 相加溢出;正解:留足余量或判断不可达再转移。
- 误区:计数用 -INF;正解:计数不可达为 0。
追问
- Q:价值可为负怎么办? A:-INF 要小于最小合法值。
- Q:哨兵参与取 min 会怎样? A:不可达被误选,需隔离。
02.7.2.4-018 多状态维度怎么合并设计?
一句话结论
把决策前提拆成互斥状态(持股、方向、胜负、特征标记),各状态存最优/概率/计数;状态间按合法动作转移;维度过多时合并可推导项,评估状态空间。
概念解释
- 互斥状态。
- 状态转移网。
原理流程
- 列情形类别。
- 各状态独立存值。
- 动作触发转移。
代码 / 示例
状态:持有/未持有;特征:数位和;胜负:胜/负
常见误区
- 误区:多状态塞一个变量;正解:分开记录。
- 误区:状态间非法转移未拦截;正解:按约束判断。
追问
- Q:状态维爆炸怎么办? A:合并冗余或换题型。
- Q:多状态初始化? A:不可达哨兵,初态置基准。
02.7.2.4-019 非常规 DP 怎么识别?
一句话结论
只要能定义状态、枚举末步决策、满足无后效性,都可 DP:概率、期望、博弈、数位、状压、树形都是变体;识别关键仍是状态定义与转移,结构决定维度组织。
概念解释
- 通用五步法。
- 变体按状态组织。
原理流程
- 找状态与末步决策。
- 判断无后效性。
- 选对应变体写法。
代码 / 图示
概率/期望/博弈/数位/状压/树形 → 状态 + 转移变体
常见误区
- 误区:非常规题不能 DP;正解:满足三条件即可。
- 误区:跳过状态定义直接套模板;正解:先定状态含义。
追问
- Q:有环状态能直接 DP 吗? A:需无环或解方程。
- Q:怎么判断后效性? A:后续是否只依赖当前状态。
02.7.2.4-020 DP 综合选型 checklist 有哪些?
一句话结论
选型顺序:是否有最优子结构与重叠子问题 → 状态是前缀/结尾/容量/区间/树/集合/数位 → 末步决策与转移 → 初始化与顺序 → 复杂度是否可行;不满足则换贪心/回溯/数学结论。
概念解释
- 适用性 → 类型 → 推导 → 可行性。
原理流程
- 核对 DP 三条件。
- 归类 DP 类型。
- 估状态空间与复杂度。
代码 / 示例
条件 → 类型(线性/背包/子序列/区间/树形/状压/数位) → 转移 → 复杂度
常见误区
- 误区:上来就写代码;正解:先定类型与状态。
- 误区:复杂度不可行仍硬填 DP;正解:评估 n 与状态空间。
追问
- Q:DP 不行还能怎么办? A:贪心、回溯枚举、数学公式、图算法。
- Q:面试怎么讲选型? A:先说条件判断,再给状态与复杂度。