首页 > 代码库 > leetcode------Climbing Stairs

leetcode------Climbing Stairs

标题:Climbing Stairs
通过率:34%
难度:简单

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?

刚拿到这个题,看完后第一反应是跟我算法课上学的那个回溯一样,就是0-1背包问题。树形结构就是1或者2 然后判断到终点没有。然后我感觉我想多了,应该不会是这种题型,无奈上网查了下思路,根据提示我拿纸写了几下:

1、n=0时,就是没有方法。

2、n=1时,只能走一步了。一种方法,

3、n=2时,可以直接走两步,或者一步一步走,

写到这里还是看不出来原因,接着写:

4、n=3时,先走一步,或者先走两步,先走一步后剩下的就回归到n=2,先走一步就回归到n=1;

5、n=4时,先走一步回归到n=3,先走两步回归到n=2;

由此可以看出,先走这一步是关键,只可能是两种,先走一步,或者先走两步,于是总结到了

f(n)=f(n-1)+f(n-2),让其一步一步的回归。写到这里很明显是个费波拉挈数列,网上再去查,这个就是斐波拉契数列的简单应用。

直接看代码:

 1 public class Solution { 2     public int climbStairs(int n) { 3         if(n==0||n==1||n==2)return n; 4         int [] array=new int[n+1]; 5         array[0]=0; 6         array[1]=1; 7         array[2]=2; 8         for(int i=3;i<=n;i++){ 9             array[i]=array[i-1]+array[i-2];10         }11         return array[n];12             }13 }

 

leetcode------Climbing Stairs