首页 > 其他 > 详细

[LeetCode] Climbing Stairs [24]

时间:2014-06-10 15:01:28      阅读:271      评论:0      收藏:0      [点我收藏+]

题目

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?

原题链接(点我)

解题思路

爬楼梯:一次可以爬1阶或者2阶,问爬n阶楼梯有多少方法?
这是个典型的斐波拉切应用场景,我们下面来分析下:
对于1阶,只有 1 种方法, 记为f(1);
对于2阶,记为f(2):

最后一步只爬1阶,有 f(1);

最后一步一次爬2阶,即一步上来,这是1中方法;

综合下来 f(2) = f(1) +1 = 2;

对于3阶,记为f(3):

最有一步只爬1阶,有f(2)种方法

最后一步一次爬2阶,有f(1)种方法;

综合下来 f(3) = f(1) + f(2) = 3

对于4阶,记为f(4):

最有一步只爬1阶,有f(3)种方法

最后一步一次爬2阶,有f(2)种方法;

综合下来 f(4) = f(3) + f(2)

....
对于n阶,记为f(n):

最有一步只爬1阶,有f(n-1)种方法

最后一步一次爬2阶,有f(n-2)种方法;

综合下来 f(n) = f(n-1) + f(n-2).

想必通过以上分析,你应该能够看明白了,就是一个斐波拉切问题。

代码实现:

class Solution {
public:
    int climbStairs(int n) {
         if(n==0) return 0;
         if(n==1) return 1;
         if(n==2) return 2;
         int n1=1, n2 = 2;
         int sum = 0;
         for(int i=3;i<=n; ++i){
             sum = n1 + n2;
             n1 = n2;
             n2 = sum;
         }
         return sum;
    }
};

如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我
bubuko.com,布布扣
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/29562769 )

[LeetCode] Climbing Stairs [24],布布扣,bubuko.com

[LeetCode] Climbing Stairs [24]

原文:http://blog.csdn.net/swagle/article/details/29562769

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!