动态规划面试题总结：状态转移、背包、子序列与 Java 模板

发表于2019-09-20|计算机基础

|浏览量:

动态规划适合具有重叠子问题和最优子结构的问题。它把递归搜索中的重复状态保存下来，使每个状态只求一次。关键不在背公式，而在定义 dp 的含义：它必须足以描述后续决策所需的信息。

标准步骤是：确定状态；列出选择；写转移方程；设置边界；决定遍历顺序；判断是否能压缩空间。以台阶计数为例，若每次走一或两级，dp[i] 表示到达第 i 级的方法数，则最后一步来自 i-1 或 i-2，所以 dp[i]=dp[i-1]+dp[i-2]。

背包问题尤其依赖顺序。0/1 背包中每件物品只能使用一次，一维数组的容量必须倒序遍历，避免当前物品被重复读取；完全背包允许重复使用，容量通常正序。子序列问题常把 dp[i] 或 dp[i][j] 定义为以某位置结尾或两个前缀上的答案。

若有 S 个状态、每个状态枚举 T 个选择，时间通常为 O(ST)，空间为状态表大小。记忆化搜索与自底向上 DP 在渐近复杂度上常相同：前者接近自然递归且只访问可达状态，后者无栈开销且遍历可控。

误区包括状态含义含糊、初始化与定义冲突、只写方程不说明遍历依赖、盲目空间压缩覆盖尚未使用的值，以及把所有最优化问题都套 DP。小结：先用一句完整中文定义状态，再从“最后一步发生什么”推导转移，正确性会比背模板可靠。

文章作者: Dai Wei

文章链接: https://www.daiwei.biz/knowledge/cs-basics/algorithms/dynamic-programming/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Dai Wei！

算法动态规划

扫码打赏

微信
支付宝

相关推荐

贪心算法面试题总结：区间贪心、跳跃游戏与证明思路

贪心算法在每一步选当前看来最有利的方案，并且不回头修改。它能成立的前提是局部最优可以扩展为全局最优；因此“看起来合理”不是证明，必须说明该选择不会排除更优答案。区间调度是典型例子：希望选择最多个互不重叠区间，应按结束时间升序，每次选择与上一个不冲突且结束最早的区间。它给后续留下最大空间。交换论证可说明：任何最优解的第一个区间，都可替换为结束更早的选择而不减少后续数量。跳跃类问题常维护当前能到达的最远位置。扫描到 i 时，若 i 已超过最远边界则不可达；否则更新 far=max(far,i+nums[i])。这不是枚举具体路径，而是压缩所有可达路径的信息。分配、合并和区间覆盖题也常通过排序后维护一个最有利边界解决。排序通常占 O(n log n)，排序后的单次扫描为 O(n)；若输入已按需要排序，整体可降为线性。额外空间取决于排序实现和是否复制数据。证明贪心可使用交换论证、领先性质或反证法。若无法证明，且早期选择会影响未来收益，就应考虑动态规划或搜索。误区是见到“最大、最小”便贪心、只凭样例确信策略，以及忽略相等端点是否冲突。小结：明确候选、选择标准和可行性边界，再给出...

时间复杂度和空间复杂度面试指南：Big O、递归复杂度与常见误区

复杂度描述输入规模增长时资源消耗的趋势，而不是程序精确运行秒数。Big O 给出渐近上界，分析时通常忽略常数和低阶项，因此 3n+20 记作 O(n)，但工程上常数、缓存和数据分布仍会影响真实表现。顺序语句复杂度相加后取主导项；独立嵌套循环通常相乘；每轮将规模减半的循环是 O(log n)。不过不能只数循环层数：内层若总共只移动 n 次，双层写法仍可能是 O(n)。递归可画递归树：二分每层一个规模减半的问题，共 log n 层；归并每层总工作量为 n，有 log n 层，所以是 O(n log n)。空间复杂度只统计随输入增长的额外空间。固定数量变量是 O(1)；长度为 n 的辅助数组是 O(n)；递归即便没有容器，也要计算调用栈。例如深度为 n 的递归占 O(n) 栈空间，平衡树递归深度通常为 O(log n)。输出本身是否计入，要在表达时说明口径。最好、平均和最坏复杂度不可混为一谈。哈希表查询平均接近 O(1)，碰撞严重时可能退化；快速排序平均 O(n log n)，极端分区会到 O(n²)。摊还分析则把偶尔昂贵的扩容分摊到多次操作，动态数组追加因而可称摊还 O(1...

几道常见的字符串算法题

字符串可视为字符序列，但工程上必须先确认字符模型：按字节、Unicode 码点还是用户看到的字素处理。纯 ASCII 题可用定长频次数组，字符集不确定时更适合哈希表，不能默认一个 char 就等于一个完整字符。常见模型有四类。字符计数用于异位词和首次唯一字符；双指针适合回文、反转与有序字符串；滑动窗口维护连续子串的约束；模式匹配则关注如何避免主串指针反复回退。朴素匹配最坏 O(nm)，KMP 通过模式串的前缀信息，在失配时复用已知匹配，预处理与搜索合计 O(n+m)。回文判断可从两端向中间走，忽略规则外字符后比较；最长回文子串可从每个中心向两侧扩展，时间 O(n²)、空间 O(1)。无重复最长子串用窗口记录字符最后位置，右端加入重复字符时，把左端跳到旧位置之后，整体 O(n)。字符串拼接也有实践成本。循环中反复创建不可变字符串可能产生二次方复制，应使用可变缓冲区。哈希统计的空间是 O(字符集大小)，字符集固定时可视为常数，但表达时最好说明前提。误区包括混淆子串与子序列、窗口收缩后忘记更新计数、Unicode 处理不当、KMP 前缀表定义前后不一致，以及使用切片导致隐藏...

算法专题：面试刷题路线、核心模板与 LeetCode 高频题

算法学习不是记答案，而是把题目翻译成模型。数组与字符串常对应双指针、滑动窗口和前缀和；有序性提示二分；“所有方案”常用回溯；局部选择可能是贪心；重复子问题则指向动态规划。树和图的核心是 DFS、BFS，优先队列适合持续取得极值，并查集适合动态连通。一条有效路线是先掌握复杂度、数组、链表、栈、队列和哈希表，再学习排序、二分、递归与树遍历，最后进入回溯、贪心、动态规划和图算法。每学一种方法，都应整理四件事：适用信号、不变量、标准步骤、时间与空间代价。做题时先写暴力方案，它给出正确性基线；随后寻找重复计算、无效枚举或可利用的顺序。通用过程可写成：明确输入输出和边界；估算规模允许的复杂度；选择数据结构；写出循环或递归不变量；用空输入、单元素、重复值和极端值验证；最后分析复杂度。错题复盘应记录“为何没识别模型”，而不是抄代码。常见误区包括只刷数量、不隔日重做；背模板却不知道退出条件；把哈希操作永远视为 O(1)；过早追求最优而没有可运行基线。面试表达也应先说思路与正确性，再写代码和测试。小结：题库只是训练素材，真正可迁移的是模型、不变量和复杂度意识。能从新题中识别旧结构，才算形...

剑指offer部分编程题

面试题训练的重点是把约束转换成结构。二维有序矩阵可从右上角开始：目标更小就左移，更大就下移，每一步排除一行或一列，时间 O(m+n)。链表反转维护三个指针；树的重建依靠前序确定根、中序划分左右子树。数组旋转最小值可利用局部单调性二分，但重复值会让边界判断失去方向，此时只能保守缩小区间。栈的压入弹出序列验证，可用辅助栈模拟：按压入顺序推进，每次栈顶等于当前弹出值就持续弹出，最终全部匹配才合法。连续子数组最大和可维护“以当前位置结尾的最大和”，转移为继续累加或从当前数重新开始。复杂度表达应对应机制：矩阵搜索不访问每个格子，而是最多移动行列之和；树重建若每次在线性查中序根会到 O(n²)，用哈希表记录下标可降为 O(n)；辅助栈验证为 O(n) 时间和 O(n) 空间。解题时先复述输入、输出及空值约定，再给暴力基线，随后指出利用的有序性、重复状态或数据结构。写完应测试空输入、单元素、重复值、全负数、退化树和整数溢出。若题目允许修改输入，也要主动说明。误区是背住某道题的代码，却无法解释边界为何移动；或者只报最终复杂度，不交代隐藏的库调用。小结：题目集合并非知识点清单，真正要练...

回溯算法面试题总结：组合、排列、子集、剪枝与 Java 模板

回溯是深度优先搜索的一种写法：把候选方案看成一棵决策树，每层做一次选择，发现不可行就撤销，回到上一个分叉。组合关心选哪些，排列还关心顺序，子集则常在每个节点都收集答案。统一步骤是：判断终止并记录快照；枚举当前层候选；跳过不合法选择；加入路径；递归下一层；撤销路径。伪代码如下： 1234567search(state): if complete(state): save(copy(path)) for choice in candidates(state): if invalid(choice): continue apply(choice) search(nextState) undo(choice) 去重必须分清层级。同一树层避免选相同值，可在排序后跳过相邻重复候选；同一路径避免重复使用元素，则用 used 数组。剪枝来自约束：剩余元素不足、当前和已超目标、当前方案不会优于最优解时，应提前返回。排序往往让这些判断更早生效。若每个元素都有选或不选两种可能，搜索规模约 O(2^n)；全排列可达 O(n!)，保存每个答案还要乘路径复制成本。递归栈...

评论

数据加载中