07
05/2015
[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?
解题思路：
动态规划，类似于斐波那契数列。
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];
}
};转载请注明：康瑞部落 » [LeetCode] Climbing Stairs
0 条评论