leetcode-70.爬楼梯

Points

斐波那契
动态规划

题意

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
示例 3：
输入： 4
输出： 5
解释： 有五种方法可以爬到楼顶。
1.   1 1 1 1 
2.   2 1 1 
3.   1 2 1
4.   1 1 2
5.   2 2

算法

本题算法思想参考自 https://www.cnblogs.com/k-li/p/5543108.html 精辟！

算一下前几个结果，我们会发现这样的规律 1 2 3 5 8 13 21 34 55 ......

即 cliimbStairs(n) = cliimbStairs(n-1) + cliimbStairs(n-2);

code

最近更新的代码

 1 class Solution {
 2 public:
 3     //递归方法:递归很可能要栈溢出
 4     int jumpFloor1(int n) {
 5         if(n == 0)
 6             return 0;
 7         if(n == 1)
 8             return 1;
 9         if(n == 2)
10             return 2;
11         return jumpFloor(n-2)+jumpFloor(n-1);
12     }
13     //非递归版的,运行时间也很快
14     int jumpFloor(int n)
15     {
16         if(n == 0)
17             return 0;
18         if(n == 1)
19             return 1;
20         if(n == 2)
21             return 2;
22         int a = 1, b = 2;
23         int res;
24         for(int i=3; i<=n; i++)
25         {
26             res = a + b;
27             a = b;
28             b = res;
29         }
30         return res;
31     }
32     //如果是一步可以爬2/3级呢
33     int jumpFloor2_3(int n)
34     {
35         if(n <= 1)
36             return 0;
37         if(n == 2)
38             return 1;
39         if(n == 3)
40             return 1;
41         int a = 0, b = 1, c = 1;
42         int res = 0;
43         for(int i=4; i<=n; i++)
44         {
45             res = a + b;
46             a = b;
47             b = c;
48             c = res;
49         }
50         return res;
51     }
52 };

下面是远古（垃圾）代码

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

后来重写了一次，精简了一些！（不要用较大数比如50去测试，int 已经爆了。既然给的是int返回值，证明样例较小。）

 1 class Solution {
 2 public:
 3     int climbStairs(int n) {
 4         if(n < 3)
 5             return n;
 6         long res = 0;
 7         int i = 3, a = 1, b = 2;
 8         while((i++) <= n)
 9         {
10             res = a + b;
11             a = b;
12             b = res;
13         }
14         return res;
15     }
16 };