动态规划经典例题：三步问题、第 N 个泰波那契数与最小花费爬楼梯

注意：for 循环的起点是 i == 3 终点是 i = n

空间优化

滚动数组 当在填 dp 表的时候，每次计算只需要前三个值，再前面的值都没用，所占的空间也就浪费了，这时候就可以用滚动数组

/**
 * 利用滚动数组
 * 进行空间优化
 *
 * @param n
 * @return
 */
public int tribonacci2(int n) {
    // 处理一下边界情况
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    int a = 0, b = 1, c = 1, d = 0;
    for (int i = 3; i <= n; i++) {
        d = a + b + c; // 滚动操作
        a = b;
        b = c;
        c = d;
    }
    return d;
}

除了上面的两个点之外，注意：d 必须是在 for 循环之外定义，不能在循环里面，要不然是一个局部变量，最后无法接收返回值。返回值是 d，不是 n

2. 三步问题

面试题 08.01. 三步问题 - 力扣（LeetCode）

题目解析

算法原理

1. 状态表示：dp[i] 代表上到第 i 阶共有多少种方法
   • 经验：以某个位置为起点或结尾…
   • 题目要求：…
   • 本题是以 i 位置为结尾
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
   • 以 i 位置状态，最近的一步，来划分问题
   • dp[i]
     1. 从 (i - 1)—>i == dp[i-1] 种
     2. 从 (i - 2)—>i == dp[i-2] 种
     3. 从 (i - 3)—>i == dp[i-3] 种
3. 初始化：dp[1] = 1; dp[2] = 2; dp[3] = 4;
4. 填表顺序：从左往右
5. 返回值：dp[n]

代码编写

public int waysToStep(int n) {
    int MOD = (int) 1e9 + 7;
    // 处理边界情况
    if (n == 1 || n == 2) return n;
    if (n == 3) return 4;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= n; i++) {
        dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
    }
    return dp[n];
}

注意：取模的写法结果是在每次进行了加法运算之后就要进行取模（所以这里需要取两次模）因为每次进行运算都有可能会溢出

3. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

题目解析

首先需要找到楼顶在哪，在数组最后一个元素的下一位

• 我们看示例 1，如果楼顶是数组最后一个元素，那最小花费应该是从 10 直接到 20，一共 10 元 当走到最后一个元素的下一位才算走到终点，走到最后一个元素不算

算法原理

解法一

1. 确定状态表示
   • 经验：以 i 位置为结尾
   • 题目要求
   • dp[i] 表示到达 i 位置时的最小花费
2. 状态转移方程
   • 思考方向：用之前或者之后的状态，推导出 dp[i] 的状态
     • 之前：dp[i-1]、dp[i-2]…
     • 之后：dp[i+1]、dp[i+2]…
   • 经验：根据最近的一步，来划分问题
     • 要么先到 i-1 位置，然后支付 cost[i-1]，走一步到达 i 位置 ==> dp[i-1] + cost[i-1]
     • 要么先到 i-2 位置，然后支付 cost[i-2]，走两步到达 i 位置 ==> dp[i-2] + cost[i-2]
   • dp[i] = min((dp[i-1] + cost[i-1]), (dp[i-2] + cost[i-2]))
3. 初始化
   • 保证填表的时候不越界
   • 初始化前两个位置
4. 填表顺序
   • 从左向右（从左向右推）
5. 返回值
   • 返回 dp[n]

解法二

就是换了一种状态表示

1. 确定状态表示
   • 经验：以 i 位置为起点
   • 题目要求
   • dp[i] 表示从 i 出发，到达楼顶的最小花费
2. 状态转移方程
   • 支付 cost[i] 之后，往后走一步，从 i+1 的位置出发，到达终点 ==> cost[i] + dp[i+1]
   • 支付 cost[i] 之后，往后走两步，从 i+2 的位置出发，到达终点 ==> cost[i] + dp[i+2]
   • dp[i] = min ((cost[i] + dp[i+1]), cost[i] + dp[i+2])
3. 初始化
   • 因为需要用到 i+1 和 i+2 位置的值，所以我们应该先初始化后面的值
   • dp[n-1] = cost[n-1]
   • dp[n-2] = cost[n-2]
4. 填表顺序
   • 从右往左
5. 返回值
   • min(dp[0], dp[1])

代码编写

解法一：

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));
    }
    return dp[n];
}

解法二：

public int minCostClimbingStairs2(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n];
    dp[n - 1] = cost[n - 1];
    dp[n - 2] = cost[n - 2];
    for (int i = n - 3; i >= 0; i--) {
        dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
    }
    return Math.min(dp[0], dp[1]);
}