首页 > 代码库 > Climbing Stairs <LeetCode>

Climbing Stairs <LeetCode>

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:下面用的是递归的方法,但是会超时

 

 1 class Solution { 2 public: 3     int total_steps=0; 4     int climbStairs(int n) { 5         if(n==0) 6         { 7             total_steps++; 8         } 9         else10         {11             if(n>=1)12             {13                climbStairs(n-1);14             }15             if(n>=2)16             {17                climbStairs(n-2);18             }19         }20         return total_steps;21     }22 };

 

 

2:用动态规划,解决了问题,代码如下:

 

 1 class Solution { 2 public: 3     int total_steps=0; 4     int climbStairs(int n) { 5     if(n==1)   return 1; 6     if(n==2)   return 2; 7     int solutions[1000]; 8     solutions[0]=0; 9     solutions[1]=1;10     solutions[2]=2;11     int i=3;12     while(i<=n)13     {14         solutions[i]=solutions[i-1]+solutions[i-2];15         i++;16     }17     return solutions[n];18     }19 };

 

Climbing Stairs <LeetCode>