《动态规划：从“傻傻穷举”到“过目不忘”的修仙之路》-北京尧图网络

递归像“查字典”查一个词发现要先查另一个词另一个词又要查第三个词直到查到最简单的词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 创建二维数组的标准方式。初始化边界是新手最容易漏掉的地方漏了就会逻辑错误。谢谢

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

相关推荐

OSPF LSA 4/5/7 实战解析：3类特殊区域配置与LSA过滤效果对比

TMC7300与PIC18F45K22的BDC电机控制方案详解

Claude Code 2026安装指南：CLI环境适配与能力验证

更多资讯

大模型推理成本暴跌99.7%：技术拆解与低成本部署实战

深度学习艺术风格迁移实战：VGG19与Gram矩阵原理、复现与避坑指南

基于LangChain与ChatGLM-6B的本地知识库问答系统搭建指南

深入浅出IP协议：从地址规划到静态配置与排障实践

自由开发者的技术近况：SSE选型、性能优化与排错实战

CC Switch 完全指南：一键切换 Codex 模型服务商与报错排查

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？