#P4031. 爬楼梯
-
ID: 2247
Tried: 902
Accepted: 366
Difficulty: 3
-
算法标签>动态规划
爬楼梯
题解
题面描述
给定一个整数 n,表示到达楼顶需要经过 n 阶台阶。每次你可以选择爬 1 阶或 2 阶。求有多少种不同的方法可以爬到楼顶。
思路
本题可以采用动态规划来解决。设 dp[i] 表示爬到第 i 阶的方法数,有如下递推公式:
- 当爬到第 i 阶时,上一步可能从第 i−1 阶迈一步上来,也可能从第 i−2 阶跨两步上来,因此有:dp[i]=dp[i−1]+dp[i−2]
- 初始条件:dp[1]=1,dp[2]=2(当 n≤2 时直接返回 n)。
这实际上就是斐波那契数列的变形,时间复杂度为 O(n),空间复杂度可以降到 O(1)。
代码分析
-
变量说明
- dp1:表示前一阶的方法数,即 dp[i−2]。
- dp2:表示当前阶的方法数,即 dp[i−1]。
- dp:临时变量,用来存储 dp1+dp2 得到的 dp[i]。
-
递推过程
从 i=3 开始,每一步将 dp[i] 计算出来,然后更新 dp1 和 dp2,直到 i=n。 -
ACM 模式
主函数中使用标准输入输出,保证能够正确处理输入输出。
C++
#include <iostream>
using namespace std;
// 使用 Solution 类包装功能函数,符合 LeetCode 风格
class Solution {
public:
// 函数功能:计算爬楼梯的方法数
int climbStairs(int n) {
// 如果 $n$ 小于等于 2,直接返回 $n$
if(n <= 2) return n;
// 初始化 dp 数组中的前两个状态
int dp1 = 1; // 对应 $dp[1]$
int dp2 = 2; // 对应 $dp[2]$
// 从 $i = 3$ 开始进行状态转移
for(int i = 3; i <= n; i++){
int dp = dp1 + dp2; // 状态转移方程 $dp[i] = dp[i-1] + dp[i-2]$
dp1 = dp2; // 更新 $dp[i-2]$
dp2 = dp; // 更新 $dp[i-1]$
}
return dp2; // 返回 $dp[n]$
}
};
int main(){
int n;
// 读取输入的阶数
cin >> n;
Solution sol;
// 输出结果
cout << sol.climbStairs(n) << endl;
return 0;
}
Python
# 定义 Solution 类,封装爬楼梯的方法
class Solution:
def climbStairs(self, n: int) -> int:
# 如果 $n$ 小于等于 2,直接返回 $n$
if n <= 2:
return n
dp1, dp2 = 1, 2 # 分别对应 $dp[1]$ 和 $dp[2]$
# 从 $i = 3$ 开始,进行动态规划状态转移
for i in range(3, n + 1):
dp = dp1 + dp2 # $dp[i] = dp[i-1] + dp[i-2]$
dp1, dp2 = dp2, dp # 更新状态
return dp2
if __name__ == "__main__":
# 读取输入的阶数
n = int(input())
sol = Solution()
# 输出结果
print(sol.climbStairs(n))
Java
import java.util.Scanner;
// 主类,包含 ACM 模式的输入输出
public class Main {
// 定义 Solution 类,封装爬楼梯的方法
static class Solution {
public int climbStairs(int n) {
// 如果 $n$ 小于等于 2,直接返回 $n$
if (n <= 2) return n;
int dp1 = 1; // 对应 $dp[1]$
int dp2 = 2; // 对应 $dp[2]$
// 从 $i = 3$ 开始进行状态转移
for (int i = 3; i <= n; i++) {
int dp = dp1 + dp2; // 状态转移方程:$dp[i] = dp[i-1] + dp[i-2]$
dp1 = dp2; // 更新 $dp[i-2]$
dp2 = dp; // 更新 $dp[i-1]$
}
return dp2; // 返回 $dp[n]$
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入的阶数
int n = sc.nextInt();
Solution sol = new Solution();
// 输出结果
System.out.println(sol.climbStairs(n));
sc.close();
}
}
题目内容
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
输入描述
输入一个整数n表示需要n阶你才能到达楼顶。
输出描述
样例1
输入
2
输出
2
说明
有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
样例2
输入
3
输出
3
说明
有三种方法可以爬到楼顶。
- 1 阶 + 1阶 + 1 阶
- 1 阶 + 2阶
- 2 阶 + 1 阶
提示
- 1<=n<=45