509. 斐波那契数

题目描述

返回第 n 个斐波那契数

按照 dp 五部曲来

1. 确定dp数组（dp table）以及下标的含义
2. int[] dp = new int[n + 1];
3. dp[i] 表示第 i 个 fib
4. 确定状态转移方程：dp[i] = dp[i- 1] + dp[i - 2]
5. 初始化：dp[0] = 0; dp[1] = 1;
6. 确定遍历顺序：从左到右
7. dp长度为9时 dp元素为：0、1、1、2、3、5、8、13、21

70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

和 509.斐波那契数很类似，当前台阶的步数可以由于前两个台阶之和决定。

即，当前台阶由前一步台阶跳一步而来或者由前两步台阶一次跳两步而来。

为什么不能由前两步台阶分别跳两个一步到当前台阶而来呢？

因为前两步台阶跳一步之后就到了当前台阶的前一步台阶，仍然相当于是从当前台阶的前一步台阶跳一步而来的。。。

746. 使用最小花费爬楼梯

dp 五部曲

1. dp[i] 表示上第 i 层楼梯最小花费
2. 状态转移方程 : dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. 初始化： dp[0] = dp[1] = 0;
4. 顺序：从左向右
5. 打印日志
6. 如果cost 为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}
7. 对应 dp 应为 {0, 0, 1, 2, 2, 3, 3, 4, 4, 5}

注意：

这里不能直接 return dp[len - 1]，顶峰为最后一个元素后面，但是这里的 dp[n-1] 还没到达顶峰.

顶峰需要从 dp[n-1]再走一步，或者从dp[n-2]一次走两步

应该 return Math.min(dp[len - 1] + cost[len - 1], cost[len - 2] + dp[len - 2]);