[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?

思路：

简单秒杀DP题。加入ret[i]表示到达step i的方法数，由于step i只能从step i-1或step i-1分别爬1和2步到达，所以：

1. ret[i] = ret[i-1] + ret[i-2]

2. 起始条件：ret[1] = 1, ret[2] = 2

3. 事实上由于ret[i]只由前两个结果决定，并不需要储存整个队列。

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: int climbStairs(int n) { if(n<=0) return 0; int p1 = 1, p2 =1; for(int i=2; i<=n; i++) { int temp = p1+p2; p1 = p2; p2 = temp; } return p2; } };