闯关leetcode——70. Climbing Stairs

2025/12/17 4:53:57 来源：https://blog.csdn.net/breaksoftware/article/details/142102831 浏览: 次关键词：闯关leetcode——70. Climbing Stairs

大纲

题目
- 地址
- 内容
解题
- 代码地址

题目

地址

https://leetcode.com/problems/climbing-stairs/description/

内容

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1 step + 1 step
2 steps
Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints:

1 <= n <= 45

解题

这题其实是一道数学题。假设有个一函数f(x)可以算出当有x个台阶时有几个方案。那么f(1)是1（即一次走1步）；f(2)是3（即走2次一步，或者1次两步）。那么f(3)是由：f(2)+走一次1步和f(1)+走1次两步两种情况组成——站在之前方案的台阶上去考虑新的问题。可能有人要问：为什么不是f(1)走2次一步？这是因为f(1)再走一步就到达了f(2)，这个方案被包含在f(2)中了。
所以这题最后就是f(n)=f(n-1)+f(n-2)，一个斐波那契额数列问题。

class Solution {
public:int climbStairs(int n) {int prev1 = 1, prev2 = 2;if (n == 1) {return prev1;}if (n == 2) {return prev2;}for (int i = 3; i < n; i++) {prev2 = prev1 + prev2;prev1 = prev2 - prev1;}return prev1 + prev2;}
};