动态规划专题：00：线性动态规划：爬楼梯问题实例

一、线性动态规划的定义具有线性阶段划分的动态规划算法称为线性动态规划简称线性DP。若状态包含多个维度则每个维度都是线性划分的阶段也属于线性DP。1. 核心概念解读动态规划DP是一种解决复杂问题的高效算法思想其核心是将原问题分解为相对简单的子问题并通过保存子问题的解即“状态”来避免重复计算最终获得原问题的解。“线性”的含义这里的“线性”特指问题求解过程在阶段划分上是线性的、顺序的。就像一条线从起点初始状态开始按照明确的、不可跳跃的顺序阶段1 - 阶段2 - ... - 阶段n一步步推进到终点最终状态。整个决策过程形成一个清晰的“链条”。2. 示意图解构状态图中状态0状态1 ...状态n代表了在解决问题过程中各个“时间点”或“步骤点”的情况记录。状态0是初始状态状态n是目标状态。决策图中 每一个阶段都有每一个阶段的决策决策1决策2 ...决策n代表从前一个状态向后一个状态转移时我们所做出的选择。每个决策都会产生一定的“代价”或“收益”并导致状态发生变化。阶段图中底部的阶段1阶段2 ...阶段n 正是线性划分的体现。每个阶段对应一次“决策状态转移”的过程。阶段与阶段之间首尾相接顺序固定构成了线性的求解流程。流程总结整个算法从状态0初始条件出发在阶段1根据状态0做出决策1从而更新到状态1然后在阶段2 再基于状态1做出决策2 更新到状态2 如此线性推进直至在阶段n做出决策n后到达最终的状态n问题得以解决。3. 对“多维度状态”的说明定义的第二句话是理解的难点和关键。它指出即使状态包含多个维度例如用坐标(i, j)表示位置只要每个维度的变化是按线性顺序进行遍历或递推的就仍然属于线性DP。举例在经典的“数字三角形”问题中状态是二维的(i, j)表示第i行第j列。我们通常的求解顺序是从第一行开始一行一行线性遍历i地向下计算在每一行内可能从左到右或按特定顺序线性遍历j计算每个位置的最优值。虽然状态是二维的但两个维度i和j的变化过程本身都是线性、有序的阶段划分因此它依然是线性DP。总结线性动态规划是一种将问题建模为“多阶段决策过程”的算法模型其核心特征是阶段的线性、顺序依赖性。​ 无论状态是单一变量还是多维变量只要决策推进的“时间线”或“逻辑顺序”是线性的就可以用线性DP的思路来解决。图片中的示意图正是这一单向、链式决策过程的经典可视化表示。常见的最长上升子序列、背包问题、最短路径问题等都是线性DP的典型应用。实例讲解1 超级楼梯题目描述HDU2041一个楼梯共有M级台阶刚开始时我们站在第1级台阶上若每次只可以走上一级或二级台阶则要走上第M级台阶共有多少种走法输入第1行包含一个整数N表示测试用例的个数。然后是N行数据每行都包含一个整数M1≤M≤40表示楼梯的级数。输出对每个测试实例都输出不同走法的数量。输入样例 输出样例2 12 23二、题意讲解1. 问题理解这是一个经典的动态规划问题类似于斐波那契数列问题。我们需要计算从第1级台阶走到第M级台阶的不同走法数量约束条件是每次只能向上走1级或2级台阶起始位置是第1级台阶目标位置是第M级台阶2. 关键点分析当M1时已经在第1级不需要走有1种走法不动当M2时从第1级到第2级只能走1步1级有1种走法当M3时从第1级到第3级有两种方式先走1级到第2级再走1级到第3级直接走2级到第3级因此有2种走法三、解题思路讲解1. 数学递推关系设f(n)表示从第1级走到第n级的走法数则有以下递推关系f(1) 1f(2) 1f(n) f(n-1) f(n-2)当n ≥ 3时解释要到达第n级台阶可以从第n-1级走1步上来或者从第n-2级走2步上来。2. 递归方法直接使用递推公式进行递归计算但这种方法存在大量重复计算时间复杂度为O(2^n)效率较低。3. 动态规划方法使用数组存储中间结果避免重复计算时间复杂度为O(n)效率高。四、C完整代码实现#include iostream #include vector using namespace std; // 方法一递归实现带记忆化 // 递归函数计算从第1级走到第n级的走法数 int recursiveSolution(int n, vectorint memo) { // 基本情况 if (n 1) return 1; // 已经在第1级只有1种走法 if (n 2) return 1; // 从第1级到第2级只能走1级 // 如果已经计算过直接返回结果 if (memo[n] ! -1) return memo[n]; // 递归计算f(n) f(n-1) f(n-2) memo[n] recursiveSolution(n-1, memo) recursiveSolution(n-2, memo); return memo[n]; } // 方法二动态规划实现 // 动态规划函数计算从第1级走到第n级的走法数 int dpSolution(int n) { // 如果n1或n2直接返回 if (n 1) return 1; if (n 2) return 1; // 创建dp数组dp[i]表示从第1级走到第i级的走法数 vectorint dp(n 1, 0); // 初始化基本情况 dp[1] 1; // 从第1级到第1级有1种走法不动 dp[2] 1; // 从第1级到第2级只能走1级有1种走法 // 递推计算 for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; } // 方法三空间优化的动态规划 // 由于只需要前两个状态可以优化空间复杂度到O(1) int dpOptimizedSolution(int n) { if (n 1) return 1; if (n 2) return 1; int prev2 1; // f(n-2) int prev1 1; // f(n-1) int current; // f(n) for (int i 3; i n; i) { current prev1 prev2; prev2 prev1; prev1 current; } return current; } int main() { int N; // 测试用例个数 cin N; // 存储所有测试用例 vectorint testCases(N); // 读取所有测试用例 for (int i 0; i N; i) { cin testCases[i]; } cout 递归方法带记忆化结果 endl; for (int i 0; i N; i) { int M testCases[i]; // 创建记忆化数组初始值为-1表示未计算 vectorint memo(M 1, -1); cout M M : recursiveSolution(M, memo) endl; } cout \n 动态规划方法结果 endl; for (int i 0; i N; i) { int M testCases[i]; cout M M : dpSolution(M) endl; } cout \n 空间优化的动态规划结果 endl; for (int i 0; i N; i) { int M testCases[i]; cout M M : dpOptimizedSolution(M) endl; } // 运行题目示例 cout \n 题目示例运行结果 endl; cout 输入 endl; cout 2 endl; cout 2 endl; cout 3 endl; cout \n输出 endl; vectorint memo1(3, -1); cout dpSolution(2) endl; // 输出1 cout dpSolution(3) endl; // 输出2 return 0; }五、代码详细讲解1. 递归方法带记忆化int recursiveSolution(int n, vectorint memo)参数n目标台阶级数memo记忆化数组存储已计算的结果避免重复计算实现原理基础情况n1或n2时直接返回结果递归情况f(n) f(n-1) f(n-2)记忆化将计算结果存入memo数组下次直接使用时间复杂度O(n)因为有记忆化每个f(n)只计算一次空间复杂度O(n)用于存储memo数组和递归调用栈2. 动态规划方法int dpSolution(int n)实现原理创建dp数组dp[i]表示从第1级走到第i级的走法数初始化dp[1]1, dp[2]1状态转移dp[i] dp[i-1] dp[i-2]最终返回dp[n]时间复杂度O(n)需要遍历1到n空间复杂度O(n)用于存储dp数组3. 空间优化的动态规划int dpOptimizedSolution(int n)实现原理由于递推公式只依赖前两个状态不需要保存整个dp数组使用三个变量prev2(f(n-2)), prev1(f(n-1)), current(f(n))每次迭代更新这三个变量时间复杂度O(n)空间复杂度O(1)只使用固定数量的变量4. 主函数int main()读取测试用例个数N读取N个测试用例台阶级数M分别用三种方法计算并输出结果最后运行并输出题目示例六、运行示例对于输入样例2 2 3程序输出 递归方法带记忆化结果 M 2: 1 M 3: 2 动态规划方法结果 M 2: 1 M 3: 2 空间优化的动态规划结果 M 2: 1 M 3: 2 题目示例运行结果 输入 2 2 3 输出 1 2七、复杂度对比方法时间复杂度空间复杂度优点缺点朴素递归O(2^n)O(n)实现简单大量重复计算效率极低记忆化递归O(n)O(n)避免重复计算需要额外存储空间动态规划O(n)O(n)逻辑清晰无递归开销需要O(n)数组空间优化动态规划O(n)O(1)空间最优逻辑稍复杂八、扩展思考如果每次可以走1级、2级或3级台阶递推公式变为f(n) f(n-1) f(n-2) f(n-3)如果起始位置不是第1级需要修改初始条件如果M很大如10^9需要使用矩阵快速幂方法将时间复杂度降到O(log n)这个超级楼梯问题是理解递归和动态规划的经典例题掌握了这个问题的解法对于理解更复杂的动态规划问题有很大帮助。