问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题方案

1、判断当前问题是否可以使用动态规划，是否存在最优子结构和重复子问题
第一步有两个选择，选择1个台阶或者2个台阶，如果选择了1个台阶，则剩下的就还有n-1个台阶，子问题就是n-1个台阶有多少种方法。选择2个台阶，就还有n-2个台阶有多少中方法。 所以也存在最优子结构。

2、其实根据第一步的描述，爬楼梯的问题就是求斐波那契数列，所以也存在重复子问题

f(n) = f(n-1) + f(n-2);

伪代码

使用自底向上方式求解

dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3 ; i < n ; i++){
dp[i] = dp[i-1]+dp[i-2];
}

return dp[n-1];