问题描述

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阶，第一次迈一阶，剩余的跟n-1的次数相同，或者第一次迈2阶，剩余的跟n-2的次数相同。斐波那契数列。

代码一：

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

代码二

1 public int climbStairs(int n){ 2         if(n<3) 3             return n; 4         else{ 5             int beforeOne=2,beforeTwo=1,sum = 0; 6             for(int i=3;i<=n;i++){ 7                 sum=beforeOne+beforeTwo; 8                 beforeTwo=beforeOne; 9                 beforeOne=sum;10             }11             return sum;12         }13     }

注意事项

下面的代码会超时

1 public class Solution {2     public int climbStairs(int n) {3         if(n==1||n==2)4             return n;5         else6             return climbStairs(n-1)+climbStairs(n-2);7     }8 }