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?

思路：num[i]表示要达到高度i的不同爬法，则i可以由从i-1往上爬一步或者从i-2往上爬两步达到。显然，两种爬法是完全不同的。因此，num[i] = num[i-1] + num[i-2]。可见，num其实是斐波拉契数列。

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

Climbing Stairs