您当前位置：首页 > php开源 > 综合技术 > leetcode 70 Climbing Stairs

leetcode 70 Climbing Stairs

来源：程序员人生发布时间：2015-09-07 08:19:15 阅读次数：3062次

Climbing Stairs

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?

Hide Tags

Dynamic Programming

这个题面试题还是比较常见的

讨论的帖子：

https://leetcode.com/discuss/2809/easy-solutions-for-suggestions

原理：

This problem is a Fibonacci problem. F(n)=F(n⑴)+F(n⑵); Solving this problem by recursion ,we will do a lot of same recursion. Example: F(10)=F(9)+F(8); F(9)=F(8)+F(7); we calculate F(8) twice,when n is large,this will increase as a rate of n's exponent.

So a more efficient way to solve this problem is from Bottom to Top. Calculate F(0) ,F(1); then F(2).........

人生ac最快的代码：

class Solution { public: int climbStairs(int n) { int stepone = 0; int steptwo = 1; int sum = 0; for(int i = 0;i<n;i++) { sum = stepone + steptwo; stepone = steptwo; steptwo = sum; } return sum; } };