企业官网建设流程全解析

1. LeetCode Hot 100动态规划专题解析（C++实现）

动态规划（Dynamic Programming）作为算法领域的核心思想，在LeetCode Hot 100中占据重要位置。这个专题将带您深入理解动态规划的核心套路，并通过C++实现典型题目。我曾用这套方法在3个月内将动态规划类题目正确率从40%提升到85%，关键在于掌握状态定义和转移方程的构建模式。

动态规划不是简单的记忆化递归，其本质是通过子问题的最优解推导全局最优解。理解这点区别能避免90%的初期错误。

2. 动态规划核心框架解析

2.1 动态规划三要素

任何动态规划问题都包含三个基本要素：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：递归求解时会重复计算相同子问题
3. 无后效性：当前状态只与之前状态有关，与后续决策无关

以经典的斐波那契数列为例：

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]; }

2.2 解题四步法

我总结的动态规划解题流程：

1. 定义dp数组含义（最难也最关键）
2. 确定初始条件
3. 推导状态转移方程
4. 考虑优化空间复杂度

以LeetCode 70.爬楼梯为例：

int climbStairs(int n) { if (n <= 2) return n; int prev = 1, curr = 2; // 空间优化：只保存前两个状态 for (int i = 3; i <= n; ++i) { int next = prev + curr; prev = curr; curr = next; } return curr; }

3. 典型题目分类解析

3.1 线性动态规划

3.1.1 最大子数组和（LeetCode 53）

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; }

这个解法体现了动态规划的空间优化技巧，将O(n)空间复杂度降为O(1)

3.1.2 打家劫舍系列（LeetCode 198/213）

环形排列的特殊处理：

int rob(vector<int>& nums) { if (nums.empty()) return 0; if (nums.size() == 1) return nums[0]; return max(robRange(nums, 0, nums.size()-2), robRange(nums, 1, nums.size()-1)); } int robRange(vector<int>& nums, int start, int end) { int prev = 0, curr = 0; for (int i = start; i <= end; ++i) { int temp = max(curr, prev + nums[i]); prev = curr; curr = temp; } return curr; }

3.2 二维动态规划

3.2.1 不同路径（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]; }

空间优化版本：

int uniquePaths(int m, int n) { vector<int> dp(n, 1); for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[j] += dp[j-1]; // 原地更新 } } return dp[n-1]; }

3.2.2 最小路径和（LeetCode 64）

int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); for (int i = 1; i < m; ++i) grid[i][0] += grid[i-1][0]; for (int j = 1; j < n; ++j) grid[0][j] += grid[0][j-1]; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { grid[i][j] += min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; }

4. 动态规划优化技巧

4.1 状态压缩

当状态转移只依赖有限的前几个状态时，可以使用滚动数组或变量替换来降低空间复杂度。以斐波那契数列为例：

int fib(int n) { if (n < 2) return n; int a = 0, b = 1; for (int i = 2; i <= n; ++i) { int c = a + b; a = b; b = c; } return b; }

4.2 备忘录法

对于树形DP等问题，可以采用记忆化搜索：

unordered_map<TreeNode*, int> memo; int rob(TreeNode* root) { if (!root) return 0; if (memo.count(root)) return memo[root]; int do_it = root->val; if (root->left) do_it += rob(root->left->left) + rob(root->left->right); if (root->right) do_it += rob(root->right->left) + rob(root->right->right); int not_do = rob(root->left) + rob(root->right); return memo[root] = max(do_it, not_do); }

5. 常见错误与调试技巧

5.1 初始化陷阱

错误示例（缺少边界条件检查）：

int climbStairs(int n) { vector<int> dp(n+1); dp[1] = 1; dp[2] = 2; // 当n=1时会越界 for (int i = 3; i <= n; ++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

5.2 状态转移方程错误

典型错误是混淆了状态定义和转移逻辑。例如在股票问题中，容易混淆持有股票和未持有股票的状态转移。

5.3 调试建议

1. 打印dp表：二维问题可以逐行打印dp数组
2. 小规模测试：先用简单用例验证基础逻辑
3. 边界检查：特别注意n=0,1等特殊情况
4. 空间优化前：先写出标准版，验证正确性后再优化

6. 进阶题目推荐

1. 股票买卖系列（LeetCode 121/122/123/188/309）
2. 背包问题（LeetCode 416/494）
3. 字符串DP（LeetCode 72/1143）
4. 状态机DP（LeetCode 1372）

对于每个问题，建议先自己尝试写出：

1. 暴力递归解法
2. 记忆化搜索版本
3. 标准动态规划实现
4. 空间优化版本

这种渐进式的练习能帮助深入理解动态规划的本质。我在准备面试时，通过这种方法在2周内搞定了所有动态规划题型，最终在算法面试环节获得了面试官的高度评价。