http://www.shangxueba.com/jingyan/2927097.html

[原创]LeetCode-Climbing Stairs（爬楼梯）(Java)

 

 

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? 

假设你在爬一个楼梯，该楼梯有n阶，你有两种爬法，每次爬一阶或者两阶。请问你有多少种爬法到达楼梯顶部。

思路1：递归

给定一个数n，有两种途径到达n

一，从n-1处，爬一阶楼梯到达n

二，从n-2处，爬两阶楼梯到达n

符合典型的递归思想。

结束条件，当n=1时，只有一种爬法。当n=2时，有两种爬法2+0,1+1

代码：

public static int climbStairs(int n) {

if(n == 1)

return 1;

if(n == 2)

return 2;

 

return climbStairs(n - 1) + climbStairs(n - 2);

}

提交结果：

分析：当n=44时，由于递归的层数太多，需要的内存指数级递增。这也是递归的弊端。而且n越大弊端表现的越明显。

思路：爬楼梯就是裴波那契数列

补：裴波那契数列

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

注：此时a1=0，a2=1，an=a(n-1)+a(n-2)（n>=2,n∈N*）

即：裴波那契数列的第n项的值是第n阶楼梯的爬法的种类数

public static int climbStairs(int n) {

 

    int a = 0;

    int b = 1;

    int sum = 0;

 

    for(int i = 1; i <= n; i++){

        sum = a + b;

        a = b;

        b = sum;

    }

return sum;

}