当前位置：首页 > ai >正文

Leetcode 03 java

ai 2025/7/18 6:32:24

爬楼梯算法

现在只看明白动态规划，也没有很难哟！！

题目

70. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

java题解

class Solution {public int climbStairs(int n) {int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q; q = r; r = p + q;}return r;}
}

这个爬楼梯算法实际上是一个经典的动态规划问题，也可以看作是斐波那契数列的变种。让我来详细解释一下：

问题理解

假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。问有多少种不同的方法可以爬到楼顶？

例如：

当n=2时，有两种方法：1+1 或直接 2 步
当n=3时，有三种方法：1+1+1、1+2、2+1
当n=4时，有五种方法：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2

动态规划思路

动态规划的核心是将大问题分解为小问题，并存储小问题的解避免重复计算。

对于爬楼梯问题，关键观察点是：

到达第i阶楼梯的方法数 = 到达第i-1阶的方法数（再爬 1 步） + 到达第i-2阶的方法数（再爬 2 步）
即状态转移方程：dp[i] = dp[i-1] + dp[i-2]

代码解释

你提供的代码正是基于这个思路实现的，只不过使用了滚动数组优化空间复杂度：

java

public int climbStairs(int n) {int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q;     // p 记录 dp[i-2] 的值q = r;     // q 记录 dp[i-1] 的值r = p + q; // r 计算当前 dp[i] = dp[i-1] + dp[i-2]}return r;
}

执行过程示例

以n=3为例：

初始状态：p=0, q=0, r=1
循环开始：
- i=1: p=0, q=1, r=p+q=1 → 到达第 1 阶有 1 种方法
- i=2: p=1, q=1, r=p+q=2 → 到达第 2 阶有 2 种方法
- i=3: p=1, q=2, r=p+q=3 → 到达第 3 阶有 3 种方法
返回结果：r=3