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?

 

 

1 class Solution { 2 public: 3     int climbStairs(int n) { 4         if(n==0) 5             return 0; 6         else if(n==1) 7             return 1; 8         else if(n==2) 9             return 2;10         else11             return climbStairs(n-1)+climbStairs(n-2);12     }13 };

 

 

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