1. 动态规划入门从斐波那契到背包问题动态规划Dynamic Programming是算法设计中最重要的思想之一它通过将复杂问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。很多初学者第一次接触动态规划都是在学习斐波那契数列时但实际上它的应用远不止于此。我在准备算法面试时花了整整两周时间专门研究动态规划问题。最初看到状态转移方程时完全摸不着头脑直到通过大量练习才逐渐理解其精髓。本文将分享我在LeetCode上刷题的实战经验重点解析五个经典动态规划问题。2. 爬楼梯问题斐波那契数列的经典应用2.1 问题描述与初步分析爬楼梯问题是动态规划最经典的入门题目。题目要求计算爬到n阶楼梯的不同方法数每次可以爬1或2个台阶。乍看之下这像是一个排列组合问题但实际上它完美符合动态规划的两个关键特性最优子结构第n阶的解依赖于第n-1阶和第n-2阶的解重叠子问题计算f(n)时需要重复计算f(n-1)和f(n-2)我第一次尝试时使用了递归解法int climbStairs(int n) { if (n 2) return n; return climbStairs(n-1) climbStairs(n-2); }这种解法虽然直观但时间复杂度高达O(2^n)当n45时就需要数秒才能计算出结果。2.2 动态规划解法优化2.2.1 基础DP解法改进方案是使用记忆化存储将中间结果保存下来int climbStairs(int n) { if (n 2) return n; int[] dp new int[n1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }这样时间复杂度降为O(n)空间复杂度也是O(n)。2.2.2 空间优化技巧观察发现我们只需要前两个状态因此可以进一步优化空间int climbStairs(int n) { if (n 2) return n; int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; } return b; }这种滚动数组技术将空间复杂度优化到O(1)。提示很多线性DP问题都可以用类似方法优化空间这是面试中的加分项。3. 杨辉三角二维动态规划的代表3.1 问题特点分析杨辉三角要求生成前numRows行其中每个数等于它上方两数之和。这实际上是一个二维动态规划问题状态定义dp[i][j]表示第i行第j列的值边界条件每行首尾元素为1状态转移dp[i][j] dp[i-1][j-1] dp[i-1][j]3.2 实现细节与优化基础实现如下public ListListInteger generate(int numRows) { ListListInteger res new ArrayList(); for (int i 0; i numRows; i) { ListInteger row new ArrayList(); for (int j 0; j i; j) { if (j 0 || j i) { row.add(1); } else { row.add(res.get(i-1).get(j-1) res.get(i-1).get(j)); } } res.add(row); } return res; }虽然这个问题不需要特别优化但它很好地展示了二维DP的实现模式。我在第一次实现时犯了一个错误没有正确处理j的边界条件导致数组越界。这提醒我们在处理二维DP时要特别注意边界条件。4. 打家劫舍线性DP的经典问题4.1 问题建模与状态定义打家劫舍问题要求在不触动警报的情况下获得最大收益。这需要定义合适的状态dp[i]考虑前i个房屋时能获得的最大金额状态转移dp[i] max(dp[i-1], nums[i] dp[i-2])4.2 实现与空间优化基础实现public int rob(int[] nums) { if (nums.length 0) return 0; if (nums.length 1) return nums[0]; int[] dp new int[nums.length]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i nums.length; i) { dp[i] Math.max(dp[i-1], nums[i] dp[i-2]); } return dp[nums.length-1]; }同样可以优化空间public int rob(int[] nums) { int prev2 0, prev1 0; for (int num : nums) { int curr Math.max(prev1, prev2 num); prev2 prev1; prev1 curr; } return prev1; }注意这类问题变种很多比如房屋排成环形的情况需要特殊处理首尾相连的限制条件。5. 完全平方数背包问题的变种5.1 问题转化思路这道题要求用最少的完全平方数凑出n可以看作是一个完全背包问题物品完全平方数1,4,9,...背包容量n目标恰好装满背包且物品数量最少5.2 动态规划解法状态转移方程 dp[i] min(dp[i], dp[i - jj] 1) 对所有jj i实现代码public int numSquares(int n) { int[] dp new int[n1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] 0; for (int i 1; i n; i) { for (int j 1; j*j i; j) { dp[i] Math.min(dp[i], dp[i - j*j] 1); } } return dp[n]; }这个问题的关键在于理解它如何转化为背包问题。我在第一次做时没有意识到这一点走了很多弯路。后来发现很多看似不同的问题其实都有相似的DP结构。6. 零钱兑换完全背包的典型应用6.1 问题分析与状态定义零钱兑换是更标准的完全背包问题dp[i]凑出金额i所需的最少硬币数初始化dp[0]0其他为无穷大状态转移dp[i] min(dp[i], dp[i-coin] 1)6.2 实现细节public int coinChange(int[] coins, int amount) { int[] dp new int[amount1]; Arrays.fill(dp, amount1); dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (coin i) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } } return dp[amount] amount ? -1 : dp[amount]; }常见错误忘记初始化dp[0]0或者没有处理无法兑换的情况。我在第一次提交时就因为没有处理无解情况而WA。7. 动态规划的解题框架通过这五个问题我总结出解决DP问题的通用步骤定义状态明确dp数组的含义确定状态转移方程找出dp[i]与之前状态的关系初始化设置边界条件确定计算顺序确保计算当前状态时所需的状态已计算考虑空间优化看是否能减少空间复杂度8. 常见错误与调试技巧在练习过程中我遇到了各种错误总结出以下调试方法打印DP表对于小规模输入打印整个DP数组检查是否正确检查边界条件特别是n0,1等特殊情况验证状态转移手动计算几个步骤看是否符合预期空间优化后验证确保优化没有改变算法逻辑9. 动态规划的进阶学习路径掌握基础DP后可以继续学习区间DP如矩阵链乘法树形DP如二叉树中的最大路径和状态压缩DP如旅行商问题数位DP如数字1的个数统计每类问题都有其独特的状态定义和转移方式需要大量练习才能熟练掌握。
1. 动态规划入门从斐波那契到背包问题动态规划Dynamic Programming是算法设计中最重要的思想之一它通过将复杂问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。很多初学者第一次接触动态规划都是在学习斐波那契数列时但实际上它的应用远不止于此。我在准备算法面试时花了整整两周时间专门研究动态规划问题。最初看到状态转移方程时完全摸不着头脑直到通过大量练习才逐渐理解其精髓。本文将分享我在LeetCode上刷题的实战经验重点解析五个经典动态规划问题。2. 爬楼梯问题斐波那契数列的经典应用2.1 问题描述与初步分析爬楼梯问题是动态规划最经典的入门题目。题目要求计算爬到n阶楼梯的不同方法数每次可以爬1或2个台阶。乍看之下这像是一个排列组合问题但实际上它完美符合动态规划的两个关键特性最优子结构第n阶的解依赖于第n-1阶和第n-2阶的解重叠子问题计算f(n)时需要重复计算f(n-1)和f(n-2)我第一次尝试时使用了递归解法int climbStairs(int n) { if (n 2) return n; return climbStairs(n-1) climbStairs(n-2); }这种解法虽然直观但时间复杂度高达O(2^n)当n45时就需要数秒才能计算出结果。2.2 动态规划解法优化2.2.1 基础DP解法改进方案是使用记忆化存储将中间结果保存下来int climbStairs(int n) { if (n 2) return n; int[] dp new int[n1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }这样时间复杂度降为O(n)空间复杂度也是O(n)。2.2.2 空间优化技巧观察发现我们只需要前两个状态因此可以进一步优化空间int climbStairs(int n) { if (n 2) return n; int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; } return b; }这种滚动数组技术将空间复杂度优化到O(1)。提示很多线性DP问题都可以用类似方法优化空间这是面试中的加分项。3. 杨辉三角二维动态规划的代表3.1 问题特点分析杨辉三角要求生成前numRows行其中每个数等于它上方两数之和。这实际上是一个二维动态规划问题状态定义dp[i][j]表示第i行第j列的值边界条件每行首尾元素为1状态转移dp[i][j] dp[i-1][j-1] dp[i-1][j]3.2 实现细节与优化基础实现如下public ListListInteger generate(int numRows) { ListListInteger res new ArrayList(); for (int i 0; i numRows; i) { ListInteger row new ArrayList(); for (int j 0; j i; j) { if (j 0 || j i) { row.add(1); } else { row.add(res.get(i-1).get(j-1) res.get(i-1).get(j)); } } res.add(row); } return res; }虽然这个问题不需要特别优化但它很好地展示了二维DP的实现模式。我在第一次实现时犯了一个错误没有正确处理j的边界条件导致数组越界。这提醒我们在处理二维DP时要特别注意边界条件。4. 打家劫舍线性DP的经典问题4.1 问题建模与状态定义打家劫舍问题要求在不触动警报的情况下获得最大收益。这需要定义合适的状态dp[i]考虑前i个房屋时能获得的最大金额状态转移dp[i] max(dp[i-1], nums[i] dp[i-2])4.2 实现与空间优化基础实现public int rob(int[] nums) { if (nums.length 0) return 0; if (nums.length 1) return nums[0]; int[] dp new int[nums.length]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i nums.length; i) { dp[i] Math.max(dp[i-1], nums[i] dp[i-2]); } return dp[nums.length-1]; }同样可以优化空间public int rob(int[] nums) { int prev2 0, prev1 0; for (int num : nums) { int curr Math.max(prev1, prev2 num); prev2 prev1; prev1 curr; } return prev1; }注意这类问题变种很多比如房屋排成环形的情况需要特殊处理首尾相连的限制条件。5. 完全平方数背包问题的变种5.1 问题转化思路这道题要求用最少的完全平方数凑出n可以看作是一个完全背包问题物品完全平方数1,4,9,...背包容量n目标恰好装满背包且物品数量最少5.2 动态规划解法状态转移方程 dp[i] min(dp[i], dp[i - jj] 1) 对所有jj i实现代码public int numSquares(int n) { int[] dp new int[n1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] 0; for (int i 1; i n; i) { for (int j 1; j*j i; j) { dp[i] Math.min(dp[i], dp[i - j*j] 1); } } return dp[n]; }这个问题的关键在于理解它如何转化为背包问题。我在第一次做时没有意识到这一点走了很多弯路。后来发现很多看似不同的问题其实都有相似的DP结构。6. 零钱兑换完全背包的典型应用6.1 问题分析与状态定义零钱兑换是更标准的完全背包问题dp[i]凑出金额i所需的最少硬币数初始化dp[0]0其他为无穷大状态转移dp[i] min(dp[i], dp[i-coin] 1)6.2 实现细节public int coinChange(int[] coins, int amount) { int[] dp new int[amount1]; Arrays.fill(dp, amount1); dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (coin i) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } } return dp[amount] amount ? -1 : dp[amount]; }常见错误忘记初始化dp[0]0或者没有处理无法兑换的情况。我在第一次提交时就因为没有处理无解情况而WA。7. 动态规划的解题框架通过这五个问题我总结出解决DP问题的通用步骤定义状态明确dp数组的含义确定状态转移方程找出dp[i]与之前状态的关系初始化设置边界条件确定计算顺序确保计算当前状态时所需的状态已计算考虑空间优化看是否能减少空间复杂度8. 常见错误与调试技巧在练习过程中我遇到了各种错误总结出以下调试方法打印DP表对于小规模输入打印整个DP数组检查是否正确检查边界条件特别是n0,1等特殊情况验证状态转移手动计算几个步骤看是否符合预期空间优化后验证确保优化没有改变算法逻辑9. 动态规划的进阶学习路径掌握基础DP后可以继续学习区间DP如矩阵链乘法树形DP如二叉树中的最大路径和状态压缩DP如旅行商问题数位DP如数字1的个数统计每类问题都有其独特的状态定义和转移方式需要大量练习才能熟练掌握。
