罗罗编程学习记录
本页内容 展开查看

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] 满足条件数。

原理流程

  1. 实现 F(x) 统计 0~x 合法数。
  2. 数位 DP 逐位填。
  3. 区间 = 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:是否仍是前导零。
  • 特征:题目累计量。

原理流程

  1. 列数位约束。
  2. 确定需要记录的特征。
  3. 组成 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. 转数位。
  2. 到末位按特征返回 1/0。
  3. 枚举当前位累加递归。

代码 / 示例

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. 记录上一位。
  2. 当前位按约束枚举。
  3. 累加合法分支。

代码 / 示例

选 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 维度。

概念解释

  • 累计特征:数位和。
  • 末位判定。

原理流程

  1. 状态带 sum。
  2. 逐位累加 d。
  3. 末位比对 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 天然按上界统计,差分避免分别处理左右边界。

概念解释

  • 前缀函数。
  • 差分相减。

原理流程

  1. 实现 F(x)。
  2. 右前缀减左前缀。
  3. 处理 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 逐位处理更直接。

概念解释

  • 上界约束。
  • 逐位特征。

原理流程

  1. 判断是否有数值上界。
  2. 有界数位约束用数位 DP。
  3. 无界用组合公式。

代码 / 图示

≤n 的合法数 → 数位 DP;不限上界 → 组合计数

常见误区

  • 误区:用组合公式处理 tight;正解:上界截断需逐位判断。
  • 误区:数位 DP 统计连续值;正解:统计满足数位特征的个数。

追问

  • Q:数位 DP 能求最大合法数吗? A:可按位贪心构造,不只是计数。
  • Q:进制可变吗? A:可转任意进制数位。

02.7.2.4-008 前导零怎么处理?

一句话结论

leading 标记当前是否仍全为前导零;前导零不参与数位和、相邻特征等统计;遇到首个非零数字关闭 leading;全零数按题意决定是否计入。

概念解释

  • 前导零:高位补零。
  • 首非零:特征开始计数。

原理流程

  1. 初始 leading=true。
  2. 当前位 0 且 leading 保持。
  3. 非零关闭标记。

代码 / 示例

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 且当前位等于上界位。

概念解释

  • 紧约束:前缀相同。
  • 松弛:前缀已小。

原理流程

  1. 初始 tight=true。
  2. 按 tight 定当前位上限。
  3. 更新下一代 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 与数位绑定。

概念解释

  • 缓存键。
  • 按上界重置。

原理流程

  1. 开 memo 表。
  2. 命中非 tight 返回。
  3. 计算后回填。

代码 / 示例

// f(x) 内部新建 memo,避免跨上界复用

常见误区

  • 误区:多组查询共用 memo 不清;正解:上界不同需重置。
  • 误区:memo 哨兵与合法计数冲突;正解:用 -1 标记未算。

追问

  • Q:末位返回值口径? A:满足特征 1,否则 0。
  • Q:缓存维度漏 leading 会怎样? A:前导零口径错乱。

02.7.2.4-011 博弈 DP(Nim 概念)怎么看必胜必败态?

一句话结论

博弈中状态分必胜态(存在一步走到必败态)与必败态(所有走向都是必胜态);终点必败;DP/递推按状态转移标记;Nim 用异或和判断,属于博弈结论而非枚举 DP。

概念解释

  • 必胜态:有合法步到必败。
  • 必败态:任意步到必胜。

原理流程

  1. 标记终点必败。
  2. 枚举可行步。
  3. 按定义判胜负态。

代码 / 示例

win(s) = 存在 t ∈ next(s) 使 !win(t)

常见误区

  • 误区:必胜态定义反;正解:能走到必败才必胜。
  • 误区:把平局当必败;正解:无平局规则下才二分胜负。

追问

  • Q:Nim 结论是什么? A:异或和非零先手必胜。
  • Q:博弈 DP 状态空间大吗? A:组合状态可能指数,需数学结论。

02.7.2.4-012 概率 DP 状态怎么定义?

一句话结论

概率 DP 状态存到达某情形的概率;转移按概率加权累加;初始状态概率 1,其余 0;末态取目标概率;常见于路径概率、抽奖、随机过程题。

概念解释

  • 概率值。
  • 加权转移。

原理流程

  1. 定义情形概率。
  2. 按分支概率累加。
  3. 取目标状态。

代码 / 示例

dp[next] += dp[cur] * p;

常见误区

  • 误区:概率取最大;正解:概率是求和加权。
  • 误区:分支概率和不为 1;正解:核对题目概率口径。

追问

  • Q:概率 DP 与最值 DP 区别? A:累加 vs 取极值。
  • Q:精度问题? A:浮点累计注意误差。

02.7.2.4-013 期望 DP 怎么转移?

一句话结论

期望线性性:E[cur] = Σ p·(代价 + E[next]);状态存期望代价/收益;转移按分支概率加权平均;期望可自底向上或记忆化求解。

概念解释

  • 期望:概率加权平均。
  • 线性性:可分层累加。

原理流程

  1. 定义状态期望。
  2. 枚举分支概率与代价。
  3. 加权求和。

代码 / 示例

E[cur] = Σ p_i * (cost_i + E[next_i])

常见误区

  • 误区:期望取最大分支;正解:按概率平均。
  • 误区:循环转移无解;正解:有环期望需解方程,非简单填表。

追问

  • Q:期望能叠加吗? A:期望线性性支持分项累加。
  • Q:状态有环怎么办? A:列方程求解,记忆化需无环。

02.7.2.4-014 概率状态转移要注意什么?

一句话结论

确认分支互斥且概率和为 1;浮点精度与累计顺序;不可达状态概率 0;多步过程按层/状态递推;概率 DP 不丢弃任何合法分支。

概念解释

  • 概率完备。
  • 浮点口径。

原理流程

  1. 核对分支概率。
  2. 初始化初态。
  3. 逐层加权更新。

代码 / 示例

p1 + p2 = 1;dp 按转移加权

常见误区

  • 误区:概率当计数累加;正解:乘分支概率。
  • 误区:浮点直接判等;正解:按容差比较。

追问

  • Q:概率 DP 复杂度? A:状态数 × 分支数。
  • Q:多源初态怎么设? A:各初态概率按题意分配。

02.7.2.4-015 博弈必胜态/必败态怎么推?

一句话结论

终点无步可走为必败;当前态若有一步进入必败态则必胜;若所有步都进入必胜态则必败;按状态逆序/记忆化标记;两类状态互斥穷尽。

概念解释

  • 终态:必败。
  • 递推规则。

原理流程

  1. 标终态必败。
  2. 反向推必胜/必败。
  3. 目标状态判定。

代码 / 示例

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);树形博弈在节点上记胜负/最优选择;二者都是把博弈状态挂到结构上,按子结构合并胜负值。

概念解释

  • 结构状态:区间/节点。
  • 零和合并。

原理流程

  1. 状态挂结构单元。
  2. 子结构胜负上交。
  3. 当前态按规则判定。

代码 / 示例

区间:dp[i][j] 相对优势;树形:节点选/不选胜负

常见误区

  • 误区:博弈只看当前步;正解:需子结构结果支撑。
  • 误区:相对优势方向取反错误;正解:后手视角取反。

追问

  • Q:博弈 DP 与普通最值 DP 区别? A:对手最优对抗,转移含取反。
  • Q:常见结构? A:区间、树、 Nim 堆。

02.7.2.4-017 DP 中 INF 怎么选取?

一句话结论

最值不可达状态用足够小的 -INF(最大值用 INF),绝对值大于任何合法结果且相加不溢出;计数不可达为 0;初始化后转移跳过不可达;注意负价值场景。

概念解释

  • 哨兵:不可达。
  • 不溢出。

原理流程

  1. 估合法结果范围。
  2. 选哨兵绝对值足够大。
  3. 转移避免哨兵参与非法合并。

代码 / 示例

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 多状态维度怎么合并设计?

一句话结论

把决策前提拆成互斥状态(持股、方向、胜负、特征标记),各状态存最优/概率/计数;状态间按合法动作转移;维度过多时合并可推导项,评估状态空间。

概念解释

  • 互斥状态。
  • 状态转移网。

原理流程

  1. 列情形类别。
  2. 各状态独立存值。
  3. 动作触发转移。

代码 / 示例

状态:持有/未持有;特征:数位和;胜负:胜/负

常见误区

  • 误区:多状态塞一个变量;正解:分开记录。
  • 误区:状态间非法转移未拦截;正解:按约束判断。

追问

  • Q:状态维爆炸怎么办? A:合并冗余或换题型。
  • Q:多状态初始化? A:不可达哨兵,初态置基准。

02.7.2.4-019 非常规 DP 怎么识别?

一句话结论

只要能定义状态、枚举末步决策、满足无后效性,都可 DP:概率、期望、博弈、数位、状压、树形都是变体;识别关键仍是状态定义与转移,结构决定维度组织。

概念解释

  • 通用五步法。
  • 变体按状态组织。

原理流程

  1. 找状态与末步决策。
  2. 判断无后效性。
  3. 选对应变体写法。

代码 / 图示

概率/期望/博弈/数位/状压/树形 → 状态 + 转移变体

常见误区

  • 误区:非常规题不能 DP;正解:满足三条件即可。
  • 误区:跳过状态定义直接套模板;正解:先定状态含义。

追问

  • Q:有环状态能直接 DP 吗? A:需无环或解方程。
  • Q:怎么判断后效性? A:后续是否只依赖当前状态。

02.7.2.4-020 DP 综合选型 checklist 有哪些?

一句话结论

选型顺序:是否有最优子结构与重叠子问题 → 状态是前缀/结尾/容量/区间/树/集合/数位 → 末步决策与转移 → 初始化与顺序 → 复杂度是否可行;不满足则换贪心/回溯/数学结论。

概念解释

  • 适用性 → 类型 → 推导 → 可行性。

原理流程

  1. 核对 DP 三条件。
  2. 归类 DP 类型。
  3. 估状态空间与复杂度。

代码 / 示例

条件 → 类型(线性/背包/子序列/区间/树形/状压/数位) → 转移 → 复杂度

常见误区

  • 误区:上来就写代码;正解:先定类型与状态。
  • 误区:复杂度不可行仍硬填 DP;正解:评估 n 与状态空间。

追问

  • Q:DP 不行还能怎么办? A:贪心、回溯枚举、数学公式、图算法。
  • Q:面试怎么讲选型? A:先说条件判断,再给状态与复杂度。