70. 爬楼梯
#leetcode#动态规划#fibonacci 2025-01-31

Problem: 70. 爬楼梯

解析

当爬了n-2阶楼梯时，再爬2阶就能到达第n阶，当爬了n-1阶楼梯时，再爬1阶就能到达第n阶，所以到达第n阶的方法数就是到达第n-1阶和n-2阶的方法数之和。 (一眼斐波那契数列)

动态规划 迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//!  n,1->for循环n次，常数空间
class Solution {
 public:
  int climbStairs(int n) {
    int a = 0, b = 1, c = 0;
    for (int i = 1; i <= n; ++i) {
      c = a + b;
      a = b;
      b = c;
    }

    return c;
  }
};