1. 动态规划核心概念与训练营价值动态规划Dynamic Programming作为算法领域的核心方法论在近年的编程能力考核中占比持续攀升。根据2023年各大技术平台统计算法面试中动态规划类题目出现频率高达42%其中背包问题、股票买卖、字符串编辑距离等经典题型更是高频考点。代码随想录算法训练营第39天的内容聚焦动态规划进阶应用这正是许多学习者在算法提升过程中遇到的分水岭。我在实际刷题和教学过程中发现动态规划的理解难点往往不在于基础理论而在于状态转移方程的构建和边界条件的处理。这个阶段的训练会重点突破多重背包问题的空间优化技巧完全背包的遍历顺序玄机打家劫舍系列问题的变种识别买卖股票问题中的状态机思维关键认知动态规划不是单纯的背模板而是对问题分解和子问题复用的系统性思考。同样的递推公式遍历顺序的细微差别可能导致完全不同的时间复杂度。2. 完全背包问题深度解析2.1 经典完全背包模板完全背包与01背包的核心区别在于物品的无限次取用这导致状态转移时需要正序遍历容量。以LeetCode 518.零钱兑换II为例def change(amount, coins): dp [0] * (amount 1) dp[0] 1 for coin in coins: # 物品循环在外层 for i in range(coin, amount 1): # 正序容量遍历 dp[i] dp[i - coin] return dp[amount]这个模板有三个易错点初始化时dp[0]必须为1空集合也是一种方案物品循环必须放在外层避免排列重复计数内层循环从coin开始减少不必要的判断2.2 遍历顺序的魔法当问题变为求排列数如LeetCode 377.组合总和IV就需要调换循环顺序def combinationSum4(nums, target): dp [0] * (target 1) dp[0] 1 for i in range(1, target 1): # 容量循环在外层 for num in nums: # 物品循环在内层 if i num: dp[i] dp[i - num] return dp[target]这种差异源于动态规划的无后效性原理。当求组合时[1,2]和[2,1]视为相同需要固定物品顺序而求排列时它们被视为不同方案需要允许顺序变化。3. 打家劫舍系列问题精讲3.1 线性版本LeetCode 198基础版的递推关系直观dp[i] max(dp[i-1], dp[i-2] nums[i])但实际编码时有三个优化点可以用滚动数组将空间复杂度降至O(1)初始条件建议设置dp[-1]dp[-2]0处理边界最终返回dp[n-1]而非dp[n]索引易错点3.2 环形版本LeetCode 213环形排列的关键是拆解为两个子问题不偷最后一间房计算nums[0:n-1]不偷第一间房计算nums[1:n] 取两者最大值即可。这种分解思想也适用于其他环形DP问题。3.3 树形版本LeetCode 337树形DP需要后序遍历每个节点返回两个状态def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) rob node.val left[1] right[1] # 选择当前节点 not_rob max(left) max(right) # 不选当前节点 return (rob, not_rob) return max(dfs(root))这个解法体现了动态规划最优子结构的特性。4. 股票买卖问题状态机解法4.1 通用状态定义对于最多k次交易的股票问题可以用三维DP表示dp[i][k][0]第i天最多k次交易不持有股票dp[i][k][1]第i天最多k次交易持有股票状态转移方程dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])4.2 空间优化技巧当k无限制时如LeetCode 122可以降维到O(1)空间hold -prices[0] cash 0 for p in prices[1:]: hold max(hold, cash - p) # 保持持有或当天买入 cash max(cash, hold p) # 保持空仓或当天卖出4.3 冷冻期处理LeetCode 309引入额外状态表示冷冻期dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) # 不持有 dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i]) # 持有这里dp[i-2][0]体现了卖出后的冷冻期限制。5. 动态规划调试与优化实战5.1 打印DP表技巧当状态转移出错时可视化DP表是最有效的调试手段。以背包问题为例def print_dp_table(dp): print( .join(f{i:2} for i in range(len(dp[0])))) for i, row in enumerate(dp): print(f{i:2} .join(f{x:2} for x in row))5.2 记忆化搜索转DP模板很多DFS记忆化的问题可以转化为DP确定DFS函数的参数就是DP的状态维度递归改为迭代遍历递归边界改为DP初始化例如斐波那契数列# 记忆化搜索 memo {} def fib(n): if n in memo: return memo[n] if n 1: return n memo[n] fib(n-1) fib(n-2) return memo[n] # 转为DP def fib_dp(n): dp [0]*(n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]5.3 常见时间优化策略单调队列优化解决滑动窗口最值问题斜率优化处理特定形式的转移方程状态压缩用位运算减少空间占用预处理前缀和加速区间查询6. 动态规划思想进阶应用6.1 区间DPLeetCode 312.戳气球区间DP通常需要枚举分割点def maxCoins(nums): nums [1] nums [1] n len(nums) dp [[0]*n for _ in range(n)] for length in range(2, n): # 区间长度 for i in range(n - length): # 区间起点 j i length for k in range(i1, j): # 分割点 dp[i][j] max(dp[i][j], nums[i]*nums[k]*nums[j] dp[i][k] dp[k][j]) return dp[0][n-1]6.2 状态压缩DPLeetCode 1349.参加考试的最大学生数用二进制表示座位状态def maxStudents(seats): m, n len(seats), len(seats[0]) dp [[-1]*(1n) for _ in range(m1)] dp[0][0] 0 for i in range(1, m1): for mask in range(1n): if not is_valid(mask, seats[i-1]): continue cnt bin(mask).count(1) for prev in range(1n): if dp[i-1][prev] -1 or not check_adjacent(mask, prev): continue dp[i][mask] max(dp[i][mask], dp[i-1][prev] cnt) return max(dp[m])6.3 数位DPLeetCode 902.最大为N的数字组合典型数位DP框架def atMostNGivenDigitSet(digits, n): s str(n) k len(s) dp [0]*(k1) dp[k] 1 for i in range(k-1, -1, -1): for d in digits: if d s[i]: dp[i] len(digits) ** (k-i-1) elif d s[i]: dp[i] dp[i1] return dp[0] sum(len(digits)**i for i in range(1, k))在实际刷题过程中我建议建立自己的动态规划解题框架笔记记录每类问题的状态定义方式典型转移方程特殊处理技巧易错边界条件 这样的系统性整理比单纯刷题更有效。对于训练营的每日任务可以先尝试自己推导状态转移再对比讲解查漏补缺这样的学习路径最为扎实。
