LeetCode70 Climbing Stairs

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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

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

Note: Given n will be a positive integer.

样例

1
2
Input:
3
1
2
Output:
2

思路

上一个$n$阶的楼梯,每次可以走1或2步,问有多少种走法。

动态规划经典题,也是斐波那契数列。

令$dp[i]$为走到第$i$阶时的方案数,则$dp[i] = dp[i-1] + dp[i-2]$,也就是说第$i$阶可以从第$i-1$阶走1步 或 第$i-2$阶走2步转移过来。初始化$dp[0] = 1$,$dp[1] = 1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1, t; //不必开数组,用三个变量模拟即可
for (int i = 1; i <= n; ++i) {
t = b;
b = a + b;
a = t;
}
return a;
}
};
分享到 评论