0%

[Leetcode]70. Climbing Stairs(C++)

题目描述

题目链接:70. Climbing Stairs

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?

例子

例子 1

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

例子 2

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints

  • 1 <= n <= 45

解题思路

最基础的应用动态规划的题目。关于动态规划主要思考两个点:怎么表示状态(子问题)以及状态转移方程。在这道题中,显然状态是在到达第 n 层有几种走法。由于每次只能走 1 层或者 2 层。那么显然:

到第 n 层的前一步只能来自 n - 1 层(再走一层就到达)或者 n - 2 层(再走两层就到达)。因此到 n 层的方法为 count(n) = count(n - 1) + count(n - 2)。由此我们可以知道求解到每一层的方法数只需要知道到达前两层的方法数即可。因此通过简单地从 n = 1 计算到第 n 层即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
// 1 way to climb to first step
int last_ways = 1;
// 2 ways to climb to second step
int current_ways = 2;

for (int i = 3; i <= n; i++) {
int next_ways = last_ways + current_ways;
last_ways = current_ways;
current_ways = next_ways;
}

return current_ways;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 70.ClimbingStairs.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions