1. 动态规划与LeetCode Hot 100的关系动态规划Dynamic Programming作为算法领域的核心思想在LeetCode Hot 100中占据了约30%的题目比例。这个数据来自2023年LeetCode官方统计其中涉及动态规划的题目主要分布在数组操作、字符串处理、树形结构等场景。为什么动态规划如此重要因为它能有效解决那些具有重叠子问题和最优子结构特性的复杂问题。在C实现动态规划时我们通常需要考虑三个关键要素状态定义如何用数据结构通常是数组或哈希表表示问题的子问题状态转移方程如何从小问题的解推导出大问题的解边界条件最小子问题的解是什么以经典的斐波那契数列为例虽然可以用递归简单实现但动态规划版本的时间复杂度能从O(2^n)优化到O(n)int fib(int n) { if (n 1) return n; vectorint dp(n1); dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }提示在LeetCode环境中使用vector而非普通数组可以避免手动内存管理同时保持较好的缓存局部性。2. 动态规划基础题型解析2.1 爬楼梯问题LeetCode 70这是最经典的入门级动态规划问题。题目要求计算爬到n阶楼梯的不同方法数每次可以爬1或2阶。状态转移方程推导过程到达第i阶的方式 从i-1阶爬1阶 从i-2阶爬2阶因此dp[i] dp[i-1] dp[i-2]空间优化技巧由于当前状态只依赖前两个状态可以将O(n)空间优化到O(1)int climbStairs(int n) { if (n 2) return n; int a 1, b 2, c; for (int i 3; i n; i) { c a b; a b; b c; } return b; }2.2 最大子数组和LeetCode 53这个问题展示了动态规划在处理最优化问题时的威力。我们需要找到一个连续子数组使其和最大。关键突破点定义dp[i]为以nums[i]结尾的最大子数组和状态转移dp[i] max(nums[i], dp[i-1] nums[i])最终结果是所有dp[i]中的最大值实际编码时可以省略dp数组只维护一个变量int maxSubArray(vectorint nums) { int maxSum nums[0], currSum nums[0]; for (int i 1; i nums.size(); i) { currSum max(nums[i], currSum nums[i]); maxSum max(maxSum, currSum); } return maxSum; }注意当题目要求返回子数组本身而非只是和时需要额外记录起始和结束位置。3. 背包问题及其变种3.1 01背包问题LeetCode 416分割等和子集问题本质上是01背包的变种。我们需要判断是否可以从数组中选出若干数使其和等于总和的一半。解题步骤计算数组总和如果是奇数直接返回false定义dp[i][j]表示前i个物品能否组成和j状态转移方程不选nums[i]: dp[i][j] dp[i-1][j]选nums[i]: dp[i][j] dp[i-1][j-nums[i]]空间优化版本一维数组bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2) return false; int target sum / 2; vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; --j) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; }3.2 完全背包问题LeetCode 322零钱兑换问题展示了完全背包的特点每种物品可以无限次使用。我们需要找出组成amount的最少硬币数。关键区别内层循环变为正序与01背包的反序对比初始化时dp[0] 0其他设为INT_MAX-1避免溢出int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, INT_MAX - 1); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] min(dp[j], dp[j - coin] 1); } } return dp[amount] INT_MAX - 1 ? -1 : dp[amount]; }4. 字符串相关动态规划4.1 最长公共子序列LeetCode 1143LCS问题展示了二维动态规划的典型应用。给定两个字符串text1和text2返回它们的最长公共子序列长度。状态定义dp[i][j]表示text1[0..i-1]和text2[0..j-1]的LCS长度状态转移方程if (text1[i-1] text2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); }空间优化技巧可以使用滚动数组将空间复杂度从O(mn)降到O(min(m,n))。4.2 编辑距离LeetCode 72这个问题计算将一个单词转换成另一个单词所需的最少操作次数插入、删除、替换。状态转移方程分析当word1[i-1] word2[j-1]时dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min( dp[i-1][j], // 删除word1[i-1] dp[i][j-1], // 插入word2[j-1] dp[i-1][j-1] // 替换 )int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; } else { dp[i][j] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; }5. 动态规划优化技巧5.1 状态压缩当状态转移只依赖有限的前几个状态时可以进行空间优化。以买卖股票的最佳时机LeetCode 121为例原始DP定义dp[i][0]第i天不持有股票的最大利润dp[i][1]第i天持有股票的最大利润优化后只需两个变量int maxProfit(vectorint prices) { int n prices.size(); int dp0 0, dp1 -prices[0]; for (int i 1; i n; i) { dp0 max(dp0, dp1 prices[i]); dp1 max(dp1, -prices[i]); } return dp0; }5.2 单调队列优化对于某些特定问题如滑动窗口最大值LeetCode 239可以使用单调队列将时间复杂度从O(nk)优化到O(n)。虽然这不是严格意义上的动态规划但体现了算法优化的思想。vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; vectorint res; for (int i 0; i nums.size(); i) { while (!q.empty() nums[q.back()] nums[i]) { q.pop_back(); } q.push_back(i); if (q.front() i - k) { q.pop_front(); } if (i k - 1) { res.push_back(nums[q.front()]); } } return res; }6. 动态规划调试技巧6.1 打印DP表格当动态规划解法出现错误时打印中间DP表格是最直接的调试方法。以最长递增子序列LeetCode 300为例int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } // 调试输出 cout i i : ; for (int x : dp) cout x ; cout endl; } return *max_element(dp.begin(), dp.end()); }6.2 边界条件检查动态规划问题中边界条件的处理往往容易出错。以不同路径问题LeetCode 62为例int uniquePaths(int m, int n) { vectorvectorint dp(m, vectorint(n, 1)); for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } return dp[m-1][n-1]; }常见错误包括忘记初始化第一行和第一列为1错误地将dp数组大小设为(m1)×(n1)但未正确处理边界返回dp[m][n]而不是dp[m-1][n-1]7. 动态规划与其他算法的结合7.1 记忆化搜索记忆化搜索是动态规划的递归实现方式适合处理树形DP问题。以打家劫舍IIILeetCode 337为例unordered_mapTreeNode*, int memo; int rob(TreeNode* root) { if (!root) return 0; if (memo.count(root)) return memo[root]; int do_rob root-val; if (root-left) { do_rob rob(root-left-left) rob(root-left-right); } if (root-right) { do_rob rob(root-right-left) rob(root-right-right); } int not_rob rob(root-left) rob(root-right); return memo[root] max(do_rob, not_rob); }7.2 贪心算法的结合有些问题可以结合贪心思想优化动态规划。以跳跃游戏LeetCode 55为例bool canJump(vectorint nums) { int reach 0; for (int i 0; i nums.size(); i) { if (i reach) return false; reach max(reach, i nums[i]); } return true; }这个解法时间复杂度O(n)比纯动态规划的O(n^2)更优。