1. 动态规划算法核心思想解析动态规划Dynamic Programming作为算法设计中的经典方法论本质上是通过将复杂问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。在解决LeetCode热题100中的动态规划问题时我们需要掌握三个关键特征识别方法最优子结构问题的最优解包含子问题的最优解。例如爬楼梯问题中到达第n阶的方案数取决于第n-1阶和第n-2阶的方案数之和。重叠子问题递归求解时会重复计算相同子问题。以斐波那契数列为例传统递归会重复计算fib(3)、fib(2)等子问题。无后效性当前状态只与之前状态有关与后续状态无关。打家劫舍问题中当前房屋的选择只与前一个房屋的决策相关。实际解题时建议先画出递归树观察是否存在大量重复计算的节点。这是判断是否适用DP的重要依据。2. 基础模型实战爬楼梯与杨辉三角2.1 爬楼梯问题LeetCode 70这是最经典的入门级DP问题题目要求计算爬到n阶楼梯的不同方法数每次可以爬1或2个台阶。状态转移方程推导过程定义dp[i]表示到达第i阶的方案数由于每次只能跨1或2阶所以dp[i] dp[i-1] dp[i-2]边界条件dp[0]1地面dp[1]1Python实现代码示例def climbStairs(n): if n 1: return 1 dp [0]*(n1) dp[0], dp[1] 1, 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]空间优化技巧实际上只需要维护前两个状态可将空间复杂度从O(n)降到O(1)def climbStairs(n): a, b 1, 1 for _ in range(2, n1): a, b b, a b return b2.2 杨辉三角LeetCode 118虽然题目看似简单但能很好训练二维DP的思维。要求生成前numRows行杨辉三角。关键观察点每行首尾元素始终为1其余元素等于上一行同列与前列元素之和状态方程dp[i][j] dp[i-1][j-1] dp[i-1][j]典型错误直接修改列表时未考虑前一行数据会被覆盖的问题。正确做法应新建临时列表def generate(numRows): res [] for i in range(numRows): row [1]*(i1) for j in range(1, i): row[j] res[i-1][j-1] res[i-1][j] res.append(row) return res3. 线性DP进阶打家劫舍系列3.1 基础版打家劫舍LeetCode 198问题描述不能连续抢劫相邻房屋求最大收益。状态设计要点dp[i]表示前i个房屋能获得的最大金额对于第i个房屋有两种选择抢劫dp[i] nums[i] dp[i-2]不抢dp[i] dp[i-1]取两者较大值dp[i] max(dp[i-1], nums[i] dp[i-2])边界条件处理dp[0] nums[0]dp[1] max(nums[0], nums[1])空间优化版实现def rob(nums): prev, curr 0, 0 for num in nums: prev, curr curr, max(curr, prev num) return curr3.2 环形房屋变种LeetCode 213新增约束条件房屋环形排列首尾视为相邻。解题技巧将问题拆分为两个子问题不抢第一个房屋求nums[1:]的最大值不抢最后一个房屋求nums[:-1]的最大值 最终取两者较大值def rob(nums): def helper(arr): prev, curr 0, 0 for num in arr: prev, curr curr, max(curr, prev num) return curr if len(nums) 1: return nums[0] return max(helper(nums[1:]), helper(nums[:-1]))4. 完全背包类问题实战4.1 完全平方数LeetCode 279问题将正整数n表示为完全平方数的和求最少需要几个数。关键突破点将问题转化为背包问题物品是1,4,9...等平方数背包容量为n完全背包特性每个平方数可重复使用dp[i]表示组成i需要的最少平方数状态转移方程 dp[i] min(dp[i], dp[i - jj] 1) 对所有jj i实现时注意初始化dp数组为极大值def numSquares(n): dp [float(inf)]*(n1) dp[0] 0 for i in range(1, n1): j 1 while j*j i: dp[i] min(dp[i], dp[i - j*j] 1) j 1 return dp[n]4.2 零钱兑换LeetCode 322与完全平方数类似但硬币面额不固定。给定不同面额的硬币和总金额求凑成总金额所需的最少硬币数。易错点需要处理无法凑出的情况返回-1初始化时dp[0]0其余为infPython实现def coinChange(coins, amount): dp [float(inf)]*(amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -15. 动态规划解题方法论5.1 四步解题框架定义状态明确dp数组的含义确定转移方程分析状态间的递推关系初始化边界条件处理初始状态和特殊情况确定计算顺序自底向上或自顶向下5.2 调试技巧打印DP表二维问题可打印矩阵观察填充过程小规模测试先用简单用例验证正确性边界检查特别注意n0,1等特殊情况5.3 复杂度优化方向空间优化滚动数组如斐波那契数列状态压缩如背包问题降维时间优化预处理数据剪枝策略数学公式推导6. 高频错误与解决方案数组越界确保dp数组大小足够通常是n1检查循环边界条件初始化错误明确dp[0]的物理意义处理特殊输入如空数组转移方程错误用具体例子手动推导验证对比经典模型找差异点顺序错误完全背包问题内层循环正序0-1背包问题内层循环逆序建议建立错题本记录每种错误类型及对应的修正方法。动态规划问题往往调试困难积累经验尤为重要。