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; vector<int> dp(n+1); 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(vector<int>& 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(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2) return false; int target = sum / 2; vector<bool> 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(vector<int>& coins, int amount) { vector<int> 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 1143）
LCS问题展示了二维动态规划的典型应用。给定两个字符串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(); vector<vector<int>> dp(m+1, vector<int>(n+1, 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(vector<int>& 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)。虽然这不是严格意义上的动态规划，但体现了算法优化的思想。
vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> q; vector<int> 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(vector<int>& nums) { int n = nums.size(); vector<int> 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) { vector<vector<int>> dp(m, vector<int>(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数组大小设为(m+1)×(n+1)但未正确处理边界
- 返回dp[m][n]而不是dp[m-1][n-1]
7. 动态规划与其他算法的结合
7.1 记忆化搜索
记忆化搜索是动态规划的递归实现方式，适合处理树形DP问题。以打家劫舍III（LeetCode 337）为例：
unordered_map<TreeNode*, 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(vector<int>& 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)更优。
