LeetCode之“动态规划”：Climbing Stairs

　　题目链接

　　题目要求

　　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?

　　做这道题容易陷入的思维就是：所有step加起来的总和是n。俺这种思维去解决这个问题的话会显得很复杂。

　　按动态规划的思维，要爬到第n阶，可以从第n-1阶爬1阶到达，也可以从第n-2阶爬2阶到达，因此爬到第n阶的方法有这么多种：

dp[n] = dp[n - ] + dp[n - ]

　　按此思维的程序代码如下：

 class Solution {

 public:

     int climbStairs(int n) {

         if(n ==  || n ==  || n == )

             return n;

         int * dp = new int[n + ];

         dp[] = ;

         dp[] = ;

         dp[] = ;

         for(int i = ; i < n + ; i++)

             dp[i] = dp[i - ] + dp[i - ];

         return dp[n];

     }

 };