假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析：
考虑该问题可拆解为父问题和子问题，上到第i级台阶时，必然是从i-1然后上一阶或i-2上两阶。
所以可以推出dp[i] = dp[i-1] + dp[i-2]，其中dp[i]为到达第i级楼梯时的不同方法。
所以自然想到可以用动态规划，状态转移方程就是dp[i] = dp[i-1] + dp[i-2](i >= 3)。
故该题可采用dp来实现。
dp五部曲：
1) 确定dp数组及含义
dp[i]表示爬到第i层楼梯总的方法数
2）确定递推公式
dp[i]= dp[i-1] + dp[i-2];
dp[i-1]表示爬到第i-1层有dp[i-1]种方法可行，那么再往上走一步就到第i层楼梯；
dp[i-2]表示爬到第i-2层有dp[i-2]种方法可行，那么再往上走2步就到第i层楼梯；
3）初始化dp
dp[0]=1;dp[1]=1;dp[2]=2;
4)确定遍历顺序
? ? ? ? 从递推公式中可以看出，遍历顺序一定是从前向后遍历的，因为只有前面的知道了 才可以计算后面的结果。
?
public int climbStairs(int n){
if(n < 3)
return n;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;i++){
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n];
}
