LeetCode

Description

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.

Solution

为了方便理解，这里n从1开始，f(n)表示在剩余n个台阶时所有可能的方案数

n=1,f(n)=1
n=2,f(n)=2
n=3,f(n)=3
n=4,f(n)=5

利用枚举抽象出一般表达式(n≥3)

f(3)=f(2)+f(1)
f(4)=f(3)+f(2)

这里，设置两个变量

one_step_last表示剩余1个台阶时可选的方案数，显然，只有1种；

two_step_last表示剩余2个台阶时可选的方案数，可以走两个one-step，也可以走一个two-step leap，因此，共有2种；

以n=3为例，此时有两种选择：

一步走1个台阶，走完之后，情况与f(2)相同
一步走2个台阶，走完之后，情况与f(1)相同

因此，对于f(3)，可选方案数为all_ways = one_step_last + two_step_last，即f(3)=f(2)+f(1)

对于n≥4的情况，直接套用上述一般表达式即可

f(4)=f(3)+f(2)
f(5)=f(4)+f(3)
…

友情提示：
对于代码中的循环语句，我的理解是：

all_ways = one_step_last + two_step_last
表示当前n=4对应的f(4)

one_step_last = two_step_last
two_step_last = all_ways
则对应于下一个循环情况，即n=4+1=5对应的f(3)和f(4)

说起来有点绕口，还请各位看官细细品味，如有错误，恳请指正！

python

 1 class Solution(object):
 2     countList = []
 3     def climbStairs(self, n):
 4         """
 5         :type n: int
 6         :rtype: int
 7         """
 8         if n == 1:
 9             return 1
10         if n == 2:
11             return 2
12 
13         one_step_last = 1
14         two_step_last = 2
15         all_ways = 0
16 
17         while n > 2:
18             all_ways = one_step_last + two_step_last
19             one_step_last = two_step_last
20             two_step_last = all_ways
21             n = n-1
22 
23         return all_ways

cpp

 1 class Solution {
 2 public:
 3     int climbStairs(int n) {
 4         if (n==1) return 1;
 5         if (n==2) return 2;
 6 
 7         int one_step_last = 1;
 8         int two_step_last = 2;
 9         int all_ways = 0;
10 
11         for (int i=3; i<=n; ++i)
12         {
13             all_ways = one_step_last + two_step_last;
14             one_step_last = two_step_last;
15             two_step_last = all_ways;
16         }
17 
18         return all_ways;
19     }
20 };

LeetCode

Description

Solution

python

cpp

Reference