【动态规划】【斐波那契数列模型】三步问题、第N个泰波那契数、使用最小花费爬楼梯

模板

算法原理

做动态规划的题目，一般会先创建一个一维数组 dp，称之为 dp表
我们想办法填满这个 dp表，里面的某个值就是最终结果

采用动态规划，一般分五步：

状态表示
1. 是什么？
  - dp 表中每一个值所表示的含义就是状态表示（通俗解释）
2. 怎么来？（非常重要）
  - 题目要求
  - 经验+题目要求（多做题）
  - 分析问题的过程中，发现重复子问题
推导状态转移方程
- dp[i]等于什么，方程就是什么
初始化
- 保证填表的时候不越界
- 根据状态转移方程进行填表
填表顺序
- 为了填写当前状态的时候，所需要的状态已经计算过了
返回值
- 题目要求+状态表示

代码编写

创建 dp 表
初始化
填表
返回值

1. 第 N 个泰波那契数

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

题目解析

Tn 等于前三项之和

算法思路

状态表示：
- 本题直接通过题目要求可知——>dp[i]表示第 i 个泰波那契数的值
根据状态表示推导状态转移方程：dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
- 依赖对象： dp[i] 依赖的是前三个状态
- 如何依赖：前三个状态之和
初始化：dp[0]=0 dp[1]=dp[2]=1
填表顺序：从左向右
返回值：dp[n]

代码编写

/**  
 * 2024-8-3 * 1. 求第 N 个泰波那契数  
 * @param n  
 * @return  
 */  
public int tribonacci(int n) {  
    //1. 创建 dp表  
    int[] dp = new int[n + 1];  
  
    //处理一下边界情况  
    if (n == 0) return 0;  
    if (n == 1 || n == 2) return 1;  
  
    //2. 初始化  
    dp[0] = 0;  
    dp[1] = dp[2] = 1;  
  
    //3. 填表  
    for (int i = 3; i <= n; i++) {  
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];  
    }  
    //4. 返回值  
    return dp[n];  
}

注意：

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

空间优化

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

/**  
 * 利用滚动数组  
 * 进行空间优化  
 *  
 * @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）

题目解析

算法原理

状态表示：dp[i] 代表上到第 i 阶共有多少种方法
- 经验：以某个位置为起点或结尾…
- 题目要求：…
- 本题是以 i 位置为结尾
状态转移方差：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] 种
初始化：dp[1] = 1; dp[2] = 2; dp[3] = 4;
填表顺序：从左往右
返回值：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 元

当走到最后一个元素的下一位才算走到终点，走到最后一个元素不算

算法原理

解法一

确定状态表示
- 经验：以 i 位置为结尾
- 题目要求
- dp[i] 表示到达 i 位置时的最小花费
状态转移方程

思考方向：用之前或者之后的状态，推导出 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]))

初始化
- 保证填表的时候不越界
- 初始化前两个位置
填表顺序
- 从左向右（从左向右推）
返回值
- 返回 dp[n]

解法二

就是换了一种状态表示

确定状态表示
- 经验：以 i 位置为起点
- 题目要求
- dp[i] 表示从 i 出发，到达楼顶的最小花费
状态转移方程

支付 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])

初始化

因为需要用到 i+1 和 i+2 位置的值，所以我们应该先初始化后面的值
dp[n-1] = cost[n-1]
dp[n-2] = cost[n-2]

填表顺序
- 从右往左
返回值
- 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]);  
}