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 else 10 { 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 };
原文：http://www.cnblogs.com/sqxw/p/3947581.html