蓝桥杯DP实战用爬楼梯和摘花生掌握动态规划五步法第一次接触动态规划时很多人都会被那些抽象的概念和复杂的递推公式吓退。但当我真正用五步法拆解了爬楼梯这道题后才发现动态规划就像搭积木——只要找到正确的搭建顺序再复杂的结构也能迎刃而解。本文将用两个蓝桥杯经典题目带你体验动态规划从入门到精通的完整思考过程。1. 动态规划的本质认知动态规划Dynamic Programming不是魔法而是一种用空间换时间的优化技术。它的核心思想很简单把大问题分解成小问题记住已经解决过的小问题答案避免重复计算。就像我们小时候做数学题会把中间结果写在草稿纸上一样。理解动态规划需要把握三个关键特征重叠子问题大问题可以分解为多个相同的小问题最优子结构大问题的最优解包含子问题的最优解状态转移当前状态可以由之前的状态推导得出以经典的斐波那契数列为例def fib(n): if n 2: return n return fib(n-1) fib(n-2) # 存在大量重复计算这个递归解法时间复杂度是O(2^n)因为计算fib(5)需要fib(4)和fib(3)而fib(4)又需要fib(3)和fib(2)...存在大量重复计算。动态规划正是为了解决这种低效问题而生。2. 动态规划五步法详解2.1 确定dp数组含义dp数组是动态规划的核心存储结构明确其含义是解题的第一步。对于爬楼梯问题假设你正在爬楼梯。需要n阶才能到达楼顶。每次可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶我们定义dp[i]爬到第i阶楼梯有dp[i]种方法这样定义后最终答案就是dp[n]。这个定义直接反映了问题的求解目标。2.2 建立递推公式递推公式是动态规划的灵魂体现了状态之间的转移关系。对于爬楼梯问题要到达第i阶只有两种可能从第i-1阶爬1阶上来从第i-2阶爬2阶上来因此递推公式为dp[i] dp[i-1] dp[i-2]这个公式完美诠释了动态规划的核心思想——当前状态由之前状态决定。2.3 初始化dp数组递推公式需要基础值才能启动。对于爬楼梯dp[0]通常认为有1种方法即不爬dp[1]只有1种方法爬1阶dp[2]有2种方法11或直接2实际编码时我们通常这样初始化vectorint dp(n1); dp[0] 1; dp[1] 1;2.4 确定遍历顺序根据递推公式dp[i]依赖于dp[i-1]和dp[i-2]所以应该从前向后遍历for(int i2; in; i){ dp[i] dp[i-1] dp[i-2]; }2.5 验证dp数组打印dp数组是调试动态规划的有效方法。对于n5dp[0]1, dp[1]1, dp[2]2, dp[3]3, dp[4]5, dp[5]8可以看到符合斐波那契数列规律验证了我们的解法。3. 摘花生问题实战现在用五步法解决蓝桥杯另一道经典题目在一个m×n的网格中每个格子有一定数量的花生。从左上角出发每次只能向右或向下移动到达右下角时最多能摘多少花生3.1 定义dp数组定义dp[i][j]从(0,0)到(i,j)能摘到的最大花生数3.2 建立递推公式对于每个格子(i,j)只能从上方(i-1,j)或左方(i,j-1)过来因此dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]3.3 初始化边界第一行和第一列比较特殊因为它们只能从一个方向过来// 初始化第一行 for(int j1; jn; j) dp[0][j] dp[0][j-1] grid[0][j]; // 初始化第一列 for(int i1; im; i) dp[i][0] dp[i-1][0] grid[i][0];3.4 确定遍历顺序由于每个格子依赖左边和上边的格子我们可以按行或按列顺序遍历for(int i1; im; i){ for(int j1; jn; j){ dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } }3.5 验证dp数组假设网格如下1 3 1 1 5 1 4 2 1计算后的dp数组1 4 5 2 9 10 6 11 12最终结果dp[2][2]12确实是最优路径(右→下→右→下)的总和。4. 动态规划优化技巧4.1 空间优化观察递推公式当前状态往往只依赖有限的几个前状态。比如爬楼梯问题中dp[i]只依赖dp[i-1]和dp[i-2]因此可以用滚动数组优化int climbStairs(int n) { if(n 2) return n; int a 1, b 2, c; for(int i3; in; i){ c a b; a b; b c; } return b; }空间复杂度从O(n)降到了O(1)。4.2 记忆化搜索对于某些问题采用递归记忆化的方式可能更直观。以摘花生为例int dfs(int i, int j, vectorvectorint grid, vectorvectorint memo){ if(i0 || j0) return 0; if(memo[i][j] ! -1) return memo[i][j]; int up dfs(i-1, j, grid, memo); int left dfs(i, j-1, grid, memo); memo[i][j] max(up, left) grid[i][j]; return memo[i][j]; }这种方法虽然时间复杂度与DP相同但更符合人类自然思维。4.3 打印决策路径有时我们需要知道最优解的路径而不仅仅是数值。可以在dp过程中记录决策struct Node{ int value; char direction; // U来自上方L来自左方 }; // 在状态转移时记录方向 if(dp[i-1][j] dp[i][j-1]){ dp[i][j].value dp[i-1][j].value grid[i][j]; dp[i][j].direction U; }else{ dp[i][j].value dp[i][j-1].value grid[i][j]; dp[i][j].direction L; }5. 常见错误与调试技巧5.1 数组越界问题在摘花生问题中处理第一行和第一列时需要特别注意边界条件。我曾犯过这样的错误// 错误示例没有处理i0和j0的情况 for(int i0; im; i){ for(int j0; jn; j){ dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } }这会导致数组越界访问。正确的做法是单独处理边界情况。5.2 初始化错误爬楼梯问题中有人会错误地初始化dp[0] 0; // 错误到达第0阶应有1种方法不爬 dp[1] 1; dp[2] 2;虽然对于n≥2能得到正确结果但dp[0]的定义不符合逻辑一致性。5.3 遍历顺序错误对于二维dp问题遍历顺序很重要。比如在解决背包问题时如果错误地先遍历容量再遍历物品可能得不到正确解。5.4 调试建议打印dp表格这是最直接的调试方法小规模测试先用小的测试用例手动计算验证边界检查特别注意n0,1等边界情况逐步验证检查每一步的状态转移是否符合预期// 调试打印示例 void printDP(vectorvectorint dp){ for(auto row : dp){ for(int num : row) cout num ; cout endl; } }6. 举一反三DP问题分类掌握了五步法后我们可以用它解决各类DP问题。常见类型包括问题类型典型题目状态定义要点线性DP最大子数组和dp[i]表示以i结尾的最优解区间DP石子合并dp[i][j]表示区间i-j的最优背包问题01背包dp[i][j]表示前i物品容量j树形DP二叉树最大路径和每个节点需要子树信息状态机DP买卖股票最佳时机定义持有/不持有状态以最大子数组和为例五步法应用定义dp[i]表示以nums[i]结尾的最大子数组和递推dp[i] max(nums[i], dp[i-1]nums[i])初始化dp[0] nums[0]遍历从前向后结果max(dp[0...n-1])int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int res dp[0]; for(int i1; in; i){ dp[i] max(nums[i], dp[i-1]nums[i]); res max(res, dp[i]); } return res; }7. 蓝桥杯备赛建议在蓝桥杯竞赛中动态规划题目通常占较大比重。根据我的参赛经验给出以下建议掌握经典模板斐波那契数列爬楼梯网格路径问题摘花生背包问题01背包、完全背包最长公共子序列编辑距离训练思维方法遇到新问题时先尝试用五步法拆解画状态转移图帮助理解从暴力递归入手再优化为DP时间管理技巧简单的DP问题控制在15分钟内解决中等难度不超过30分钟遇到难题先写部分分代码代码模板整理// 经典DP问题框架 int dp_problem(vectorint input) { int n input.size(); // 1. 定义dp数组 vectorint dp(n); // 2. 初始化 dp[0] ...; // 3. 状态转移 for(int i1; in; i){ dp[i] ... // 根据问题确定转移方程 } // 4. 返回结果 return ...; }常见优化手段滚动数组降维单调队列/栈优化斜率优化高级技巧记住动态规划能力的提升没有捷径只有通过大量练习才能真正掌握。建议从LeetCode或蓝桥杯真题中挑选20-30道不同难度的DP题目系统练习每道题都用五步法严格分析很快你就能对这类问题形成条件反射般的解题直觉。
蓝桥杯备赛别怕DP！用‘爬楼梯’和‘摘花生’两题吃透动态规划五步法（C++代码详解）
发布时间：2026/5/16 20:17:31
蓝桥杯DP实战用爬楼梯和摘花生掌握动态规划五步法第一次接触动态规划时很多人都会被那些抽象的概念和复杂的递推公式吓退。但当我真正用五步法拆解了爬楼梯这道题后才发现动态规划就像搭积木——只要找到正确的搭建顺序再复杂的结构也能迎刃而解。本文将用两个蓝桥杯经典题目带你体验动态规划从入门到精通的完整思考过程。1. 动态规划的本质认知动态规划Dynamic Programming不是魔法而是一种用空间换时间的优化技术。它的核心思想很简单把大问题分解成小问题记住已经解决过的小问题答案避免重复计算。就像我们小时候做数学题会把中间结果写在草稿纸上一样。理解动态规划需要把握三个关键特征重叠子问题大问题可以分解为多个相同的小问题最优子结构大问题的最优解包含子问题的最优解状态转移当前状态可以由之前的状态推导得出以经典的斐波那契数列为例def fib(n): if n 2: return n return fib(n-1) fib(n-2) # 存在大量重复计算这个递归解法时间复杂度是O(2^n)因为计算fib(5)需要fib(4)和fib(3)而fib(4)又需要fib(3)和fib(2)...存在大量重复计算。动态规划正是为了解决这种低效问题而生。2. 动态规划五步法详解2.1 确定dp数组含义dp数组是动态规划的核心存储结构明确其含义是解题的第一步。对于爬楼梯问题假设你正在爬楼梯。需要n阶才能到达楼顶。每次可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶我们定义dp[i]爬到第i阶楼梯有dp[i]种方法这样定义后最终答案就是dp[n]。这个定义直接反映了问题的求解目标。2.2 建立递推公式递推公式是动态规划的灵魂体现了状态之间的转移关系。对于爬楼梯问题要到达第i阶只有两种可能从第i-1阶爬1阶上来从第i-2阶爬2阶上来因此递推公式为dp[i] dp[i-1] dp[i-2]这个公式完美诠释了动态规划的核心思想——当前状态由之前状态决定。2.3 初始化dp数组递推公式需要基础值才能启动。对于爬楼梯dp[0]通常认为有1种方法即不爬dp[1]只有1种方法爬1阶dp[2]有2种方法11或直接2实际编码时我们通常这样初始化vectorint dp(n1); dp[0] 1; dp[1] 1;2.4 确定遍历顺序根据递推公式dp[i]依赖于dp[i-1]和dp[i-2]所以应该从前向后遍历for(int i2; in; i){ dp[i] dp[i-1] dp[i-2]; }2.5 验证dp数组打印dp数组是调试动态规划的有效方法。对于n5dp[0]1, dp[1]1, dp[2]2, dp[3]3, dp[4]5, dp[5]8可以看到符合斐波那契数列规律验证了我们的解法。3. 摘花生问题实战现在用五步法解决蓝桥杯另一道经典题目在一个m×n的网格中每个格子有一定数量的花生。从左上角出发每次只能向右或向下移动到达右下角时最多能摘多少花生3.1 定义dp数组定义dp[i][j]从(0,0)到(i,j)能摘到的最大花生数3.2 建立递推公式对于每个格子(i,j)只能从上方(i-1,j)或左方(i,j-1)过来因此dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]3.3 初始化边界第一行和第一列比较特殊因为它们只能从一个方向过来// 初始化第一行 for(int j1; jn; j) dp[0][j] dp[0][j-1] grid[0][j]; // 初始化第一列 for(int i1; im; i) dp[i][0] dp[i-1][0] grid[i][0];3.4 确定遍历顺序由于每个格子依赖左边和上边的格子我们可以按行或按列顺序遍历for(int i1; im; i){ for(int j1; jn; j){ dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } }3.5 验证dp数组假设网格如下1 3 1 1 5 1 4 2 1计算后的dp数组1 4 5 2 9 10 6 11 12最终结果dp[2][2]12确实是最优路径(右→下→右→下)的总和。4. 动态规划优化技巧4.1 空间优化观察递推公式当前状态往往只依赖有限的几个前状态。比如爬楼梯问题中dp[i]只依赖dp[i-1]和dp[i-2]因此可以用滚动数组优化int climbStairs(int n) { if(n 2) return n; int a 1, b 2, c; for(int i3; in; i){ c a b; a b; b c; } return b; }空间复杂度从O(n)降到了O(1)。4.2 记忆化搜索对于某些问题采用递归记忆化的方式可能更直观。以摘花生为例int dfs(int i, int j, vectorvectorint grid, vectorvectorint memo){ if(i0 || j0) return 0; if(memo[i][j] ! -1) return memo[i][j]; int up dfs(i-1, j, grid, memo); int left dfs(i, j-1, grid, memo); memo[i][j] max(up, left) grid[i][j]; return memo[i][j]; }这种方法虽然时间复杂度与DP相同但更符合人类自然思维。4.3 打印决策路径有时我们需要知道最优解的路径而不仅仅是数值。可以在dp过程中记录决策struct Node{ int value; char direction; // U来自上方L来自左方 }; // 在状态转移时记录方向 if(dp[i-1][j] dp[i][j-1]){ dp[i][j].value dp[i-1][j].value grid[i][j]; dp[i][j].direction U; }else{ dp[i][j].value dp[i][j-1].value grid[i][j]; dp[i][j].direction L; }5. 常见错误与调试技巧5.1 数组越界问题在摘花生问题中处理第一行和第一列时需要特别注意边界条件。我曾犯过这样的错误// 错误示例没有处理i0和j0的情况 for(int i0; im; i){ for(int j0; jn; j){ dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } }这会导致数组越界访问。正确的做法是单独处理边界情况。5.2 初始化错误爬楼梯问题中有人会错误地初始化dp[0] 0; // 错误到达第0阶应有1种方法不爬 dp[1] 1; dp[2] 2;虽然对于n≥2能得到正确结果但dp[0]的定义不符合逻辑一致性。5.3 遍历顺序错误对于二维dp问题遍历顺序很重要。比如在解决背包问题时如果错误地先遍历容量再遍历物品可能得不到正确解。5.4 调试建议打印dp表格这是最直接的调试方法小规模测试先用小的测试用例手动计算验证边界检查特别注意n0,1等边界情况逐步验证检查每一步的状态转移是否符合预期// 调试打印示例 void printDP(vectorvectorint dp){ for(auto row : dp){ for(int num : row) cout num ; cout endl; } }6. 举一反三DP问题分类掌握了五步法后我们可以用它解决各类DP问题。常见类型包括问题类型典型题目状态定义要点线性DP最大子数组和dp[i]表示以i结尾的最优解区间DP石子合并dp[i][j]表示区间i-j的最优背包问题01背包dp[i][j]表示前i物品容量j树形DP二叉树最大路径和每个节点需要子树信息状态机DP买卖股票最佳时机定义持有/不持有状态以最大子数组和为例五步法应用定义dp[i]表示以nums[i]结尾的最大子数组和递推dp[i] max(nums[i], dp[i-1]nums[i])初始化dp[0] nums[0]遍历从前向后结果max(dp[0...n-1])int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int res dp[0]; for(int i1; in; i){ dp[i] max(nums[i], dp[i-1]nums[i]); res max(res, dp[i]); } return res; }7. 蓝桥杯备赛建议在蓝桥杯竞赛中动态规划题目通常占较大比重。根据我的参赛经验给出以下建议掌握经典模板斐波那契数列爬楼梯网格路径问题摘花生背包问题01背包、完全背包最长公共子序列编辑距离训练思维方法遇到新问题时先尝试用五步法拆解画状态转移图帮助理解从暴力递归入手再优化为DP时间管理技巧简单的DP问题控制在15分钟内解决中等难度不超过30分钟遇到难题先写部分分代码代码模板整理// 经典DP问题框架 int dp_problem(vectorint input) { int n input.size(); // 1. 定义dp数组 vectorint dp(n); // 2. 初始化 dp[0] ...; // 3. 状态转移 for(int i1; in; i){ dp[i] ... // 根据问题确定转移方程 } // 4. 返回结果 return ...; }常见优化手段滚动数组降维单调队列/栈优化斜率优化高级技巧记住动态规划能力的提升没有捷径只有通过大量练习才能真正掌握。建议从LeetCode或蓝桥杯真题中挑选20-30道不同难度的DP题目系统练习每道题都用五步法严格分析很快你就能对这类问题形成条件反射般的解题直觉。
