LeetCode //C – 70. Climbing Stairs

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?
 

Example 1:

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

1. 1 step + 1 step
2. 2 steps

Example 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

From: LeetCode
Link: 70. Climbing Stairs

Solution:

Ideas：

• We handle the base case where n=1.
• We use two variables first and second to keep track of the number of ways to reach the current and the next step.
• We iterate from 3 to n, updating these two variables at each step. third represents the number of ways to reach the current step, which is the sum of the ways to reach the previous two steps (first + second).
• Finally, we return the value of second, which represents the number of ways to reach the top step.

Code:

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }

    int first = 1;
    int second = 2;

    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }

    return second;
}

代码007普通

打赏 收藏 海报 链接