动态规划算法精讲：从基础到实战10大经典问题

1. 动态规划算法精讲从爬楼梯到最长有效括号动态规划Dynamic Programming是解决算法问题的核心思想之一特别适用于具有重叠子问题和最优子结构特性的场景。本文将深入解析10个经典动态规划问题从基础的爬楼梯问题到复杂的最长有效括号问题带你掌握动态规划的核心思想和实现技巧。1.1 动态规划基础概念动态规划通过将原问题分解为相对简单的子问题的方式来解决复杂问题。它通常用于优化问题如寻找最大值、最小值或计数问题。动态规划的核心思想包括状态定义明确dp数组或变量表示的含义状态转移方程确定如何从已知状态推导出新状态初始条件确定最简单情况的解边界条件处理特殊情况提示理解动态规划的关键在于识别问题的状态和状态转移关系。每个动态规划问题都可以看作是一个状态机的演进过程。2. 基础动态规划问题解析2.1 爬楼梯问题爬楼梯是最经典的动态规划入门问题。题目描述假设你正在爬楼梯需要n步才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法可以爬到楼顶。解法分析class Solution { public int climbStairs(int n) { int[] dp new int[n1]; dp[0] 1; // 初始状态到达第0阶有1种方法不爬 dp[1] 1; // 到达第1阶只有1种方法 for(int i2; in; i){ dp[i] dp[i-1] dp[i-2]; // 状态转移方程 } return dp[n]; } }关键点状态定义dp[i]表示爬到第i阶楼梯的方法数状态转移到达第i阶可以从第i-1阶爬1步或从第i-2阶爬2步空间优化实际上只需要维护前两个状态可将空间复杂度优化到O(1)常见错误忘记初始化dp[0]和dp[1]数组越界当n0或n1时不理解为什么dp[0]1数学上空集也是一种解2.2 杨辉三角问题杨辉三角是另一个展示动态规划思想的经典问题。给定一个非负整数numRows生成杨辉三角的前numRows行。解法分析class Solution { public ListListInteger generate(int numRows) { ListListInteger list new ArrayList(); for(int i0; inumRows; i){ ListInteger temp new ArrayList(); for(int j0; ji; j){ if(j0 || ji) temp.add(1); // 边界条件 else temp.add(list.get(i-1).get(j-1) list.get(i-1).get(j)); // 状态转移 } list.add(temp); } return list; } }关键点每行的第一个和最后一个元素都是1其他元素等于上一行同列和前一个列元素之和使用List嵌套List来存储结果便于动态扩展优化技巧可以预分配空间避免频繁扩容对于只需要特定行的情况可以使用组合数公式直接计算3. 一维动态规划进阶3.1 打家劫舍问题打家劫舍问题描述给定一个代表每个房屋存放金额的非负整数数组计算在不触动警报装置的情况下即不能偷相邻的两个房屋能够偷窃到的最高金额。解法分析class Solution { public int rob(int[] nums) { 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 i2; inums.length; i){ dp[i] Math.max(dp[i-1], dp[i-2] nums[i]); } return dp[nums.length-1]; } }关键点状态定义dp[i]表示偷到第i个房屋时的最大金额状态转移对于第i个房屋可以选择偷则不能偷i-1或不偷保持i-1的状态空间优化同样可以只维护前两个状态变种问题房屋排成环形首尾相连房屋形成二叉树结构3.2 完全平方数问题给定正整数n找到若干个完全平方数如1,4,9,16,...使得它们的和等于n。需要让组成和的完全平方数的个数最少。解法分析class Solution { public int numSquares(int n) { int[] dp new int[n1]; Arrays.fill(dp, 10001); // 初始化为较大值 dp[0] 0; // 边界条件 for(int i1; in; i){ for(int j1; j*ji; j){ dp[i] Math.min(dp[i-j*j]1, dp[i]); } } return dp[n]; } }关键点状态定义dp[i]表示组成i所需的最少完全平方数个数状态转移对于每个i尝试所有可能的完全平方数j*j数学优化根据四平方和定理任何自然数都可以表示为4个以内完全平方数的和4. 背包问题变种4.1 零钱兑换问题给定不同面额的硬币和一个总金额计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。解法分析class Solution { public int coinChange(int[] coins, int amount) { Arrays.sort(coins); // 排序优化 int[] dp new int[amount1]; Arrays.fill(dp, amount1); // 初始化为不可能的大值 dp[0] 0; // 边界条件 for(int i1; iamount; i){ for(int j0; jcoins.length; j){ if(coins[j] i) break; // 提前终止 dp[i] Math.min(dp[i], dp[i-coins[j]]1); } } return dp[amount] amount1 ? -1 : dp[amount]; } }关键点状态定义dp[i]表示凑成金额i所需的最少硬币数状态转移对于每个金额i尝试所有可能的硬币面额初始化技巧使用amount1作为无穷大值便于后续比较注意事项硬币数组是否需要排序取决于具体实现当amount为0时的特殊情况处理4.2 单词拆分问题给定一个非空字符串s和一个包含非空单词列表的字典wordDict判定s是否可以被空格拆分为一个或多个在字典中出现的单词。解法分析class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString set new HashSet(wordDict); // 使用HashSet提高查找效率 int n s.length(); boolean[] dp new boolean[n1]; dp[0] true; // 空字符串可以被拆分 for(int i1; in; i){ for(int j1; ji; j){ if(set.contains(s.substring(j-1, i)) dp[j-1]){ dp[i] true; break; // 找到一个可行解即可 } } } return dp[n]; } }关键点状态定义dp[i]表示前i个字符能否被拆分状态转移检查所有可能的分割点j优化技巧使用HashSet存储字典查找时间复杂度降为O(1)性能考虑可以预处理字典中最长单词长度优化内层循环范围对于大规模输入可以考虑Trie树等更高效的数据结构5. 序列问题与二维动态规划5.1 最长递增子序列问题给定一个无序的整数数组找到其中最长严格递增子序列的长度。解法分析class Solution { public int lengthOfLIS(int[] nums) { int[] dp new int[nums.length]; int end -1; for(int i0; inums.length; i){ if(end -1 || dp[end] nums[i]) dp[end] nums[i]; else find(nums[i], dp, end); } return end1; } public void find(int target, int[] dp, int end){ int l -1, r end1; while(l1 ! r){ int mid l (r-l)/2; if(dp[mid] target) r mid; else l mid; } dp[r] target; } }关键点维护一个递增序列dp对于每个元素如果大于dp末尾元素直接追加否则用二分查找找到合适的位置替换最终dp的长度即为最长递增子序列长度算法复杂度时间复杂度O(n log n)空间复杂度O(n)5.2 乘积最大子数组问题给你一个整数数组nums请你找出数组中乘积最大的连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。解法分析class Solution { public int maxProduct(int[] nums) { int res nums[0]; int maxVal nums[0]; int minVal nums[0]; for(int i1; inums.length; i){ int max maxVal; maxVal Math.max(nums[i], Math.max(nums[i]*maxVal, nums[i]*minVal)); res Math.max(res, maxVal); minVal Math.min(nums[i], Math.min(nums[i]*max, nums[i]*minVal)); } return res; } }关键点由于存在负数需要同时维护当前最大值和最小值状态转移时考虑三种情况当前数本身、当前数乘以前一个最大值、当前数乘以前一个最小值空间优化只需维护前一个状态边界情况数组包含0的情况数组全为负数的情况单个元素的情况6. 分割问题与括号匹配6.1 分割等和子集问题给定一个只包含正整数的非空数组判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。解法分析class Solution { public boolean canPartition(int[] nums) { int sum 0; int max 0; for(int num : nums){ sum num; max Math.max(max, num); } int target sum / 2; if(sum % 2 1 || max target) return false; boolean[] dp new boolean[target1]; dp[0] true; for(int num : nums){ for(int jtarget; jnum; j--){ // 反向遍历避免重复计算 dp[j] | dp[j-num]; } } return dp[target]; } }关键点问题转化为背包问题能否找到若干数其和为总和的一半提前判断总和为奇数直接返回false空间优化使用一维数组反向遍历优化技巧先对数组排序从大到小处理可以更快达到目标值使用位运算优化空间6.2 最长有效括号问题给定一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。动态规划解法class Solution { public int longestValidParentheses(String s) { int cnt 0, n s.length(); int[] dp new int[n1]; for(int i2; in; i){ if(s.charAt(i-1) () continue; if(s.charAt(i-2) () dp[i] 2 dp[i-2]; else { if(i-dp[i-1]-2 0 s.charAt(i-dp[i-1]-2) () dp[i] 2 dp[i-1] dp[i-dp[i-1]-2]; } cnt Math.max(cnt, dp[i]); } return cnt; } }双指针解法class Solution { public int longestValidParentheses(String s) { int n s.length(), cnt 0; int left 0, right 0; // 从左到右扫描 for(int i0; in; i){ if(s.charAt(i) () left; else right; if(right left) cnt Math.max(cnt, rightleft); if(right left){ left 0; right 0; } } // 从右到左扫描 left 0; right 0; for(int in-1; i0; i--){ if(s.charAt(i) () left; else right; if(right left) cnt Math.max(cnt, rightleft); if(right left){ left 0; right 0; } } return cnt; } }关键点动态规划解法复杂但通用双指针解法更高效但需要两次扫描注意边界条件的处理选择建议面试中优先实现双指针解法动态规划解法作为备选方案7. 动态规划问题解题方法论通过以上10个问题的分析我们可以总结出解决动态规划问题的一般步骤定义状态明确dp数组或变量的含义建立状态转移方程找出如何从已知状态推导出新状态确定初始条件设置最简单情况的解考虑边界条件处理特殊情况选择计算顺序自顶向下或自底向上空间优化考虑是否可以用滚动数组等技巧减少空间复杂度在实际应用中还需要注意以下几点先尝试用递归思路理解问题再转化为动态规划画状态转移图有助于理解复杂问题对于一维问题通常可以优化到O(1)空间二维问题可能需要考虑状态压缩技巧动态规划是一种强大的算法设计技术掌握它需要大量的练习和经验积累。建议从简单问题入手逐步挑战更复杂的问题培养对状态定义和转移的直觉。