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     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 };