Saturday, November 22, 2014

[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;
    }
};

No comments:

Post a Comment