[LeetCode] Climbing Stairs

You are climbing a stair case. It takesnsteps 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?

解题思路：

动态规划，类似于斐波那契数列。

X X X…X X X

如上图，假如我们知道了n-1个台阶的走法数目，对于第n个台阶，分两种情况：若第n个台阶单独走，那么n个台阶的走法数目就等于n-1个台阶走的数目；所第n个台阶与n-1个台阶一起走，那么n个台阶的走法数目就等于n-2个台阶的走法数目。

这里有个trick，若n=0，那么应该返回什么？从题意上来说，0个台阶应该有1种走法，那就是不需要走。而且若n=2，，为使d[2] = d[1]+d[0]，那么d[0]也应该等于1。

class Solution {public:int climbStairs(int n) {int d[n + 1];d[0] = d[1] = 1;for(int i=2; i<=n; i++){d[i] = d[i-1] + d[i-2];}return d[n];}};

躲在某一地点，想念一个站在来路，