1. 动态规划刷题实战3小时攻克14道LeetCode经典题刷算法题就像健身需要持续的系统训练。今天我用3小时集中攻克了14道动态规划题目这种高强度的专题突破对建立解题思维特别有效。动态规划DP作为算法面试的必考题型掌握其核心套路能让你在笔试面试中脱颖而出。这次刷题聚焦背包问题、股票买卖和子序列三大经典DP类型这也是大厂面试最高频的考点。我会分享每类题目的解题模板、易错点和优化技巧这些实战经验你在教科书里绝对找不到。2. 动态规划核心框架解析2.1 DP五部曲解题标准化流程动态规划的核心在于状态定义和转移方程。经过上百道题的锤炼我总结出通用解题框架确定dp数组含义90%的初学者错误源于定义模糊。比如背包问题中dp[i][j]表示前i件物品在容量j时的最大价值初始化边界条件比如dp[0][j]和dp[i][0]在背包问题中通常初始化为0推导状态转移方程这是最关键的步骤。以爬楼梯问题为例dp[i] dp[i-1] dp[i-2] # 第i阶可以从i-1或i-2阶上来确定遍历顺序01背包要倒序遍历容量完全背包则正序举例验证手动计算测试用例检查dp数组变化重要提示先用这个框架解决基础题如70.爬楼梯再挑战更复杂的变种2.2 时间复杂度优化技巧空间压缩二维dp降为一维滚动数组数学推导斐波那契数列可用矩阵快速幂优化到O(logn)剪枝策略在递归解法中加入记忆化3. 背包问题深度剖析3.1 01背包经典变种今天刷的416.分割等和子集是01背包的典型应用def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): # 关键倒序 dp[j] dp[j] or dp[j - num] return dp[target]易错点忘记总和为奇数直接返回False的判断遍历顺序错误必须倒序防止重复使用初始化时dp[0]必须为True空集合和为03.2 完全背包实战322.零钱兑换展示了完全背包的典型结构def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): # 正序遍历 dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1关键区别物品可无限取用正序遍历求最小个数时初始化为inf需要处理无解情况返回-14. 股票买卖问题套路4.1 状态机模型121.买卖股票的最佳时机展示了DP在金融问题中的应用def maxProfit(prices): n len(prices) dp [[0] * 2 for _ in range(n)] dp[0][0], dp[0][1] 0, -prices[0] for i in range(1, n): dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) # 卖出 dp[i][1] max(dp[i-1][1], -prices[i]) # 买入 return dp[-1][0]状态定义技巧dp[i][0]表示第i天不持股的最大收益dp[i][1]表示第i天持股的最大收益冷冻期问题需要增加状态维度4.2 空间优化版观察到当前状态只依赖前一个状态def maxProfit(prices): hold, not_hold -prices[0], 0 for p in prices[1:]: not_hold max(not_hold, hold p) hold max(hold, -p) return not_hold5. 子序列问题精讲5.1 最长公共子序列(LCS)1143题展示了二维DP的经典应用def longestCommonSubsequence(text1, text2): m, n len(text1), len(text2) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]关键点dp数组要比字符串长度大1处理空串不等时的转移需要取max区别于子串问题5.2 编辑距离问题72.编辑距离是字符串DP的终极挑战def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min( dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 ) return dp[m][n]操作成本分析每个操作成本为1可自定义不同权重初始化时空串到i长度需要i次操作6. 刷题效率提升方法论6.1 计时训练技巧设置25分钟专注时段番茄工作法简单题控制在15分钟内中等题不超过30分钟超时立即看题解标记需重做6.2 错题管理策略我建立的错题本包含这些字段| 题号 | 错误原因 | 正确解法要点 | 重做日期 | |------|--------------------|--------------------|-----------| | 416 | 遍历顺序错误 | 01背包必须倒序 | 2023-03-15| | 322 | 初始化值为0 | 应初始化为inf | 2023-03-16|6.3 刷题计划建议初级阶段按类型集中突破如2周专攻DP中级阶段混合题型随机练习冲刺阶段模拟真实面试随机题库计时7. 高频问题答疑7.1 为什么我的DP解法会超时常见原因重复计算未记忆化如斐波那契递归无效状态未剪枝使用了高复杂度算法本可用贪心7.2 如何判断该用DP还是贪心满足最优子结构DP/贪心都可能有无后效性DP处理有后效性问题能否局部最优推全局最优贪心的标志7.3 DP调试技巧打印dp表格验证状态转移用小测试用例手动演算对比自顶向下和自底向上结果这次集中刷题让我对DP的理解又深了一层。最大的收获是发现背包问题和股票问题其实共享同样的状态转移思想只是具体维度不同。建议每个程序员都把动态规划作为必修课它不仅能帮你通过面试更能培养强大的问题分解能力。