第一部分核心思想文字详解1. 什么是动态规划动态规划不是一种特定的算法而是一种编程思想。它的核心是通过把原问题分解为相对简单的子问题并保存子问题的解来避免重复计算从而解决复杂问题。暴力递归是“自顶向下”求解从大问题开始拆但会有大量重复计算。动态规划是“自底向上”求解从小问题开始推用数组把每一步结果存下来直接拿来用。2. 适用场景两个必要条件不是所有问题都能用DP必须同时满足最优子结构大问题的最优解可以由子问题的最优解推导出来。比如全校最高分 max高一最高分高二最高分。重叠子问题在递归求解过程中子问题会反复出现。比如斐波那契数列中fib(3)被计算了无数次。3. DP解题五步法最强心法拿到一道题按这5步走绝对不会乱定义DP数组dp[i]的含义这一步最关键。问自己dp[i]代表什么是“到达第i级台阶的方法数”还是“前i天能获得的最大利润”找出递推公式状态转移方程思考dp[i]和dp[i-1]、dp[i-2]有什么关系这是DP的灵魂。初始化base case最小的那几个值是什么比如dp[0]和dp[1]等于几确定遍历顺序是从前往后还是从后往前是遍历i还是遍历j打印DP数组验证把DP数组打印出来手动模拟前几步看看是否符合预期。第二部分三大经典DP题型及代码详解我按难度递进给你写三个最经典的模型附带详细注释。案例一一维DP入门—— 爬楼梯问题每次可以爬1或2个台阶爬到第n级有多少种不同方法思路到达第n级要么从n-1级跨1步要么从n-2级跨2步。所以dp[n] dp[n-1] dp[n-2]。pythondef climbStairs(n: int) - int: # 1. 特判边界 if n 2: return n # 2. 定义dp数组这里多开一个位置方便理解索引从0到n dp [0] * (n 1) # 3. 初始化 (Base Case) dp[1] 1 # 1级台阶只有1种走法 dp[2] 2 # 2级台阶有11 或 2共2种 # 4. 遍历顺序从前往后 for i in range(3, n 1): # 5. 状态转移方程 dp[i] dp[i - 1] dp[i - 2] return dp[n] # 空间优化滚动数组写法面试时能写这个绝对是加分项 def climbStairs_optimized(n: int) - int: if n 2: return n a, b 1, 2 # a代表dp[1], b代表dp[2] for i in range(3, n 1): a, b b, a b # 新b 旧a 旧b return b案例二二维DP进阶—— 不同路径机器人走路问题m行n列的网格机器人从左上角走到右下角只能向右或向下有多少条不同路径思路到达(i, j)只能从上方(i-1, j)或左方(i, j-1)过来。dp[i][j] dp[i-1][j] dp[i][j-1]。pythondef uniquePaths(m: int, n: int) - int: # 1. 定义二维dp数组 dp [[0] * n for _ in range(m)] # 2. 初始化第一行和第一列只有一种走法一直向右或一直向下 for i in range(m): dp[i][0] 1 for j in range(n): dp[0][j] 1 # 3. 遍历顺序双层循环从上到下从左到右 for i in range(1, m): for j in range(1, n): # 4. 状态转移方程 dp[i][j] dp[i-1][j] dp[i][j-1] return dp[m-1][n-1] # 空间压缩技巧只用一维数组逐行刷新 def uniquePaths_compressed(m: int, n: int) - int: dp [1] * n # 第一行全是1 for i in range(1, m): for j in range(1, n): # dp[j] 代表上方的值旧值dp[j-1] 代表左边的值已更新 dp[j] dp[j] dp[j-1] return dp[-1]案例三经典背包问题面试高频—— 0-1背包问题有n个物品重量w[i]价值v[i]背包容量W。求能装的最大价值。思路对于每个物品只有“拿”或“不拿”两种状态。dp[i][j]表示前i个物品在容量j下的最大价值。pythondef knapsack(weights, values, W): n len(weights) # 1. dp数组行是物品索引列是容量 dp [[0] * (W 1) for _ in range(n 1)] # 2. 遍历所有物品 for i in range(1, n 1): # 当前物品的重量和价值注意索引偏移因为dp从1开始 w weights[i-1] v values[i-1] for j in range(1, W 1): # 如果当前容量装不下这个物品直接继承上一个状态 if j w: dp[i][j] dp[i-1][j] else: # 状态转移max(不拿, 拿) # 拿的话腾出w的空间 当前价值v dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v) return dp[n][W] # 极端重要的一维滚动数组优化面试必会 def knapsack_optimized(weights, values, W): n len(weights) dp [0] * (W 1) # 注意外层遍历物品内层必须**倒序遍历**容量 # 因为正序会导致物品被重复拿取变成完全背包 for i in range(n): w weights[i] v values[i] for j in range(W, w - 1, -1): # 从大到小 dp[j] max(dp[j], dp[j - w] v) return dp[W] # 测试数据 weights [2, 3, 4, 5] values [3, 4, 5, 6] W 5 print(knapsack_optimized(weights, values, W)) # 输出 7 (选择重量23价值34)第三部分DP的难点与进阶技巧纯文字干货1. 如何区分“0-1背包”和“完全背包”0-1背包每个物品只能选一次遍历容量时用倒序for j in range(W, w-1, -1)。完全背包每个物品可以选无限次遍历容量时用正序for j in range(w, W1)。因为正序允许在同一轮循环中叠加当前物品。2. 什么时候用“二维DP”什么时候用“一维DP”如果状态只依赖上一行的数据比如背包问题都可以压缩成一维。如果状态依赖左上角、右上角等复杂位置强行压缩会增加理解难度笔试时写二维更稳妥虽然费点内存但不出错。3. 动态规划与贪心、回溯的区别贪心每一步都选当前最优局部最优不回头。适合“硬币找零”的特殊情况。回溯暴力枚举所有可能性DFS有“后悔药”。动态规划有记录的回溯用空间换时间。当问题有重叠子结构时DP碾压回溯。4. 打印路径不只是求值有时候题目要求输出具体的“路径”比如具体选了哪些物品。解决办法是维护一个path二维数组当dp[i][j]选择“拿”时记录path[i][j]True最后倒序回溯寻找答案。给你的通透理解如果把动态规划比作做数学证明题状态定义就是“设未知数X”。转移方程就是“找已知条件和未知数的关系”。初始化就是“已知的定理或公理”。遍历顺序就是“证明的逻辑顺序”。