1. 初识“上台阶”问题第一次接触“上台阶”问题时我正在准备信息学奥赛。题目看似简单假设每次可以跨1、2或3级台阶问走到第n级台阶有多少种走法。但当我尝试用递归暴力求解时程序在n30时就卡住了。这个问题其实是动态规划的经典入门案例。想象你站在楼梯前要到达第n级台阶最后一步可能是从n-1级跨1阶从n-2级跨2阶或者从n-3级跨3阶。这个思路就是递推的核心——把大问题分解为小问题。在OpenJudge和NOI的题库中这道题常作为递推算法的教学案例出现。我建议初学者先从具体例子入手n1只有1种走法跨1阶n22种11或直接跨2阶n34种1111221直接跨3阶通过这些小例子能直观感受到递推关系的存在。这也是为什么很多教练推荐用这道题作为算法思维的启蒙练习。2. 递推解法详解2.1 状态定义与初始化递推解法的关键在于正确定义状态。我们定义a[i]表示走到第i级台阶的走法总数。根据前面的分析初始条件很明确a [0] * 105 # 初始化数组 a[1] 1 a[2] 2 a[3] 4这里有个细节需要注意数组大小要足够大。在OpenJudge的测试用例中n可能达到100所以数组至少要开到105。我刚开始就因为这个细节WA了几次。2.2 递推关系建立递推公式a[i] a[i-1] a[i-2] a[i-3]看似简单但理解其背后的逻辑很重要。这相当于说所有走到i-1级的走法再跨1级就能到i级所有走到i-2级的走法直接跨2级到i级所有走到i-3级的走法直接跨3级到i级这三种情况互不重叠所以总走法数是它们的和。实现起来就是for i in range(4, 101): a[i] a[i-1] a[i-2] a[i-3]2.3 数据类型选择这里有个坑点当n100时结果会非常大。在C中如果用int会溢出必须用long long。Python虽然不用担心这个问题但在其他语言中要特别注意。我在NOI训练时就因为没注意数据类型白白丢过分。3. 记忆化递归优化3.1 暴力递归的问题最直观的解法是递归def naive_recursion(n): if n 1: return 1 if n 2: return 2 if n 3: return 4 return naive_recursion(n-1) naive_recursion(n-2) naive_recursion(n-3)但这样效率极低。计算f(30)时程序要递归调用数百万次。这是因为存在大量重复计算比如计算f(5)时会重复计算f(4)、f(3)等。3.2 引入记忆化记忆化技术就是用来解决这个问题的。我们用一个数组保存已经计算过的结果memo [0] * 105 def memoization(n): if memo[n] 0: return memo[n] if n 1: return 1 if n 2: return 2 if n 3: return 4 memo[n] memoization(n-1) memoization(n-2) memoization(n-3) return memo[n]这样每个f(n)只需要计算一次时间复杂度从指数级降到了O(n)。在实际测试中记忆化版本计算f(100)几乎是瞬间完成的。4. 两种解法的对比分析4.1 时间复杂度比较递推解法是标准的自底向上动态规划明确地按顺序计算每个a[i]。它的时间复杂度是O(n)空间复杂度也是O(n)但可以优化到O(1)如果只保留最近三个值。记忆化递归是自顶向下的动态规划通过递归缓存实现。虽然时间复杂度也是O(n)但递归调用会有额外的栈开销。不过它的代码更接近原始问题描述更容易理解。4.2 适用场景选择在竞赛中递推通常是首选因为它没有递归深度限制常数时间更优代码结构更简单但在某些复杂问题中记忆化递归可能更直观。比如当状态转移不是简单的线性递推时记忆化写法可能更容易实现。4.3 实际测试数据我用Python测试了两种解法在n100时的表现递推0.0001秒记忆化递归0.0002秒暴力递归n30时就需要5秒这个对比清楚地展示了算法优化的重要性。在信息学奥赛中同样的思路不同的实现方式可能决定能否通过时间限制。5. 算法思维的延伸5.1 变种问题探讨上台阶问题有很多变种比如每次只能跨1或2阶斐波那契数列每次能跨1到k阶某些台阶不能踩需要增加限制条件这些变种都可以用类似的递推或记忆化方法解决。我建议初学者多尝试这些变种能加深对动态规划的理解。5.2 从具体到抽象的思维过程解决这类问题的通用思路是从小规模案例入手寻找规律定义清晰的状态表示建立状态转移方程确定初始条件选择实现方式递推/记忆化这种思维模式不仅适用于台阶问题也是解决大多数动态规划问题的钥匙。我在NOI备赛时就是通过反复练习这类基础问题逐步建立起算法思维的。6. 代码实现细节6.1 递推实现要点完整的C递推实现需要注意#include iostream using namespace std; int main() { long long a[105] {0}; a[1] 1; a[2] 2; a[3] 4; for(int i4; i100; i) { a[i] a[i-1] a[i-2] a[i-3]; } int n; while(cin n n ! 0) { cout a[n] endl; } return 0; }特别注意数组初始化数据类型用long long循环从4开始输入处理方式6.2 记忆化递归实现要点记忆化版本的实现技巧#include iostream #include cstring using namespace std; long long memo[105]; long long solve(int n) { if(memo[n] ! -1) return memo[n]; if(n 1) return 1; if(n 2) return 2; if(n 3) return 4; return memo[n] solve(n-1) solve(n-2) solve(n-3); } int main() { memset(memo, -1, sizeof(memo)); int n; while(cin n n ! 0) { cout solve(n) endl; } return 0; }关键点初始化memo数组为-1表示未计算先检查是否已计算过递归终止条件保存计算结果7. 常见错误与调试技巧7.1 新手常犯错误根据我的教学经验初学者常见错误包括初始条件错误比如误认为a[3]3数组越界没开足够大的数组整数溢出没用long long输入处理不当没处理好多组测试数据递归终止条件不全漏掉某些基本情况7.2 调试建议调试这类问题时我建议先打印小规模n的结果验证正确性检查边界条件n0,1,2,3在递推循环中加入打印语句观察计算过程对于记忆化递归可以打印缓存命中情况记得我在初学时就因为没有处理好n0的输入题目中n0表示输入结束导致程序无限循环。这种细节在竞赛中会浪费大量时间。