Description:

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个台阶。

每次可以走一步或者二步。有几种方法可以到达顶层？ 

 

解答:

典型的一维动态规划问题（Dynamic Programming，DP）。

从第0个台阶走到第i个台阶的走法，可以看成一下两种走法的和：

1）从第0个台阶走到第i-1个台阶，再走1步；

2）从第0个台阶走到第i-2个台阶，再走2步；

因此，状态转移方程为：OPT(i) = OPT(i-1) + OPT(i-2)

对于基本情况：OPT(0) = 1; OPT(1) = 1。

 

下面的代码中，使用一维动态数组记录第i步的走法，直到计算出n个台阶的走法为止。

算法的效率为O(n)

 

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