递归像“查字典”查一个词发现要先查另一个词另一个词又要查第三个词直到查到最简单的词Base Case才停止。DP 像“考前抱佛脚背书”把查过的词条直接抄在 A4 纸上DP数组考试时直接看纸不用翻书。模块一斐波那契数列递归 vs 记忆化 vs 递推1. 思路讲解Why C在 C 中递归深度过深如n 10000会导致栈溢出Stack Overflow。而且 C 没有 Python 那样的字典dict天然支持我们需要手动开数组。2. 代码详解版本 A纯递归反面教材仅用于理解cppcpp#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记忆化搜索自顶向下cppcpp#include iostream #include vector using namespace std; int fibHelper(int n, vectorint 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表示未计算 vectorint memo(n 1, -1); memo[0] 0; memo[1] 1; return fibHelper(n, memo); }思路定义一个memo数组C Vector初始化为-1。进入函数先判断memo[n]是否不为-1如果是直接返回剪枝。否则计算并把结果存进memo[n]。注意这里使用了引用传参​vectorint memo避免数组拷贝的巨大开销。版本 C动态规划自底向上推荐cppcppint fib(int n) { if (n 1) return n; vectorint 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. 代码详解cppcpp#include vector using namespace std; class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorint dp(n 1); // 多开一位防止 n1 时越界 dp[1] 1; // 1阶1种 dp[2] 2; // 2阶2种 (11 或 2) for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };C 坑点如果vectorint dp(n)下标范围是[0, n-1]。如果访问dp[n]会越界。所以通常开n1方便理解。模块三最小路径和二维 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. 代码详解cppcpp#include vector #include algorithm using namespace std; class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorvectorint dp(m, vectorint(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]; } };思路拆解vectorvectorint dp(m, vectorint(n, 0));这是 C 创建二维数组的标准方式。初始化边界是新手最容易漏掉的地方漏了就会逻辑错误。谢谢