首页 > > 程序设计 > C/C++ >

爬楼梯

2018-06-17 23:13:17来源：未知阅读 ()

爬楼梯

描述：假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例:

比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

返回 3

烧脑，从一开始算法就错了，采用几乎是阶乘算法，每每导致溢出，都是Long型才能算到39，就差用数组了，错误代码如下。

class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        if(n==0)
        return 0;
        long a,c,b=n-1,sum=1,p1,p2;
        for(a=1;a<=b;a++,b--)
        {
            p1=1,p2=1;
            for(long j=1,c=b;j<a+1;j++,c--)
            {
            p1*=c;
            p2*=j;
            }
        sum+=p1/p2;
        }
        return sum;
    }
};

但经过查质料竞是另一种算法，气啊

class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        if(n==0)
        return 1;
        int sum[n];
        sum[0] = 1;
        if(n>1)
        sum[1] = 2;
        for(int i = 2;i < n;i++)
        sum[i] = sum[i-1]+sum[i-2];
        return sum[n-1];
    }
};