当前位置：首页 > news >正文

《动态规划：从“傻傻穷举”到“过目不忘”的修仙之路》

news 2026/7/11 9:00:48

递归像“查字典”，查一个词，发现要先查另一个词，另一个词又要查第三个词，直到查到最简单的词（Base Case）才停止。

DP 像“考前抱佛脚背书”，把查过的词条直接抄在 A4 纸上（DP数组），考试时直接看纸，不用翻书。

模块一：斐波那契数列（递归 vs 记忆化 vs 递推）

1. 思路讲解（Why C++？）

在 C++ 中，递归深度过深（如n > 10000）会导致栈溢出（Stack Overflow）。而且 C++ 没有 Python 那样的字典（dict）天然支持，我们需要手动开数组。

2. 代码详解

版本 A：纯递归（反面教材，仅用于理解）

cpp

#include <iostream> using namespace std; int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } int main() { cout << fib(5) << endl; // 5 return 0; }

思路：最直观的数学定义。
缺点：时间复杂度 O(2n)，存在大量重复计算。

版本 B：记忆化搜索（自顶向下）

cpp

#include <iostream> #include <vector> using namespace std; int fibHelper(int n, vector<int>& memo) { // 1. 查表：如果算过，直接返回 if (memo[n] != -1) { return memo[n]; } // 2. 计算：没算过，则计算并存入表中 memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo); return memo[n]; } int fib(int n) { if (n <= 1) return n; // 初始化备忘录，-1表示未计算 vector<int> memo(n + 1, -1); memo[0] = 0; memo[1] = 1; return fibHelper(n, memo); }

思路：
1. 定义一个memo数组（C++ Vector），初始化为-1。
2. 进入函数先判断memo[n]是否不为-1，如果是，直接返回（剪枝）。
3. 否则计算，并把结果存进memo[n]。
注意：这里使用了引用传参vector<int>& memo，避免数组拷贝的巨大开销。

版本 C：动态规划（自底向上，推荐）

cpp

int fib(int n) { if (n <= 1) return n; vector<int> dp(n + 1); // dp[i] 表示第 i 个斐波那契数 dp[0] = 0; // Base Case dp[1] = 1; // Base Case for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程 } return dp[n]; }

思路：从最小的子问题开始，一步步构建大问题的解。像织毛衣一样，一行一行织上去。

模块二：爬楼梯（理解 DP 数组定义）

1. 思路讲解

这是 DP 定义的经典题。关键在于定义dp[i]的含义：爬到第 i 阶楼梯的方法总数。

由于每次只能爬 1 或 2 阶，所以第 i 阶只能由第 i-1 阶（走 1 步）或第 i-2 阶（走 2 步）到达。

因此：dp[i] = dp[i-1] + dp[i-2]。

2. 代码详解

cpp

#include <vector> using namespace std; class Solution { public: int climbStairs(int n) { if (n <= 2) return n; vector<int> dp(n + 1); // 多开一位，防止 n=1 时越界 dp[1] = 1; // 1阶：1种 dp[2] = 2; // 2阶：2种 (1+1 或 2) for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };

C++ 坑点：如果vector<int> dp(n)，下标范围是[0, n-1]。如果访问dp[n]会越界。所以通常开n+1方便理解。

模块三：最小路径和（二维 DP 入门）

1. 思路讲解

想象一个棋盘，dp[i][j]代表从左上角(0,0)走到当前格子(i,j)的最小路径和。

要到达(i,j)，只能从上方(i-1,j)或左方(i,j-1)过来。

所以：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。

特例：第一行只能从左来，第一列只能从上来。

2. 代码详解

cpp

#include <vector> #include <algorithm> using namespace std; class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); // 1. 初始化起点 dp[0][0] = grid[0][0]; // 2. 初始化第一列（只能从上往下） for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // 3. 初始化第一行（只能从左往右） for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // 4. 填充剩余格子 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { // 核心：取上方和左方的最小值，加上当前格子的代价 dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } };