前置知识
文字讲解：动态规划理论基础
做题步骤：
- 找问题的最好方式就是把dp数组打印出来，搞清楚每一个值代表的含义
- 递推公式
- dp数组初始化、遍历顺序
509. 斐波那契数
题目链接/文字讲解：斐波那契数
题设：斐波那契数（通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
思路：动规五部曲：
要用一个一维dp数组来保存递归的结果
1.确定dp数组以及下标的含义-dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2.确定递推公式-状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
3.dp数组如何初始化
4.确定遍历顺序-dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
70. 爬楼梯
题目链接/文字讲解：爬楼梯
题设：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：动规五部曲：
定义一个一维数组来记录不同楼层的状态
1.确定dp数组以及下标的含义-dp[i]： 爬到第i层楼梯，有dp[i]种方法
2.确定递推公式-dp[i] = dp[i - 1] + dp[i - 2] 。
3.dp数组如何初始化-再回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。
题目中说了n是一个正整数，题目根本就没说n有为0的情况。
只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
4.确定遍历顺序-从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
5.举例推导dp数组
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
和斐波那契基本没区别。当然，还可以拓展一下，若是每步可走1-m怎么办，这种情况其实和背包问题相似。
746. 使用最小花费爬楼梯
题目链接/文字讲解：使用最小花费爬楼梯
题设：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
思路：动规五部曲：
1.确定dp数组以及下标的含义-dp[i]： 爬到第i层楼梯，消耗的最少费用。
2.确定递推公式-当前为第i个台阶，爬过它所需要的最少消耗为其本身消耗+min(第i-1个台阶消耗,第i-2个台阶消耗)。
3.dp数组如何初始化-再回顾一下dp[i]的定义：dp[0]=cost[0],dp[1]=cost[1]。(可以选择从0/1开始)
4.确定遍历顺序-从下往上爬，遍历顺序一定是从前向后遍历的。不需要考虑数组长度为0，1的情况。
5.举例推导dp数组。
class Solution {
public int minCostClimbingStairs(int[] cost) {
if (cost.length == 2) return Math.min(cost[1], cost[0]);
int[] dp = new int[cost.length];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}
