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的方法，一个台阶的方法次数为1次，两个台阶的方法次数为2个。n个台阶的方法可以理解成上n-2个台阶，然后2步直接上最后一步；或者上n-1个台阶，再单独上一步。
int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; return (climbStairs(n-1) + climbStairs(n-2)); }
改成DP的方法代码如下：
int climbStairs(int n) { if(n <= 2) return n; int *p = malloc(sizeof(int)*n); int i; p[0] = 1; p[1] = 2; for(i=2; i<n; i++){ p[i] = p[i-1]+p[i-2]; } return p[n-1]; }
class Solution { public: int climbStairs(int n) { if(n <= 2) { return n; } else { int* step = new int[n]; step[0] = 1; step[1] = 2; for(int i = 2; i < n; i++) { step[i] = step[i-1] + step[i-2]; } return step[n-1]; } } };
原文：http://www.cnblogs.com/zhhc/p/4351741.html