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

模板

算法原理

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

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

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

代码编写

1. 创建 dp 表
2. 初始化
3. 填表
4. 返回值

1. 第 N 个泰波那契数

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

题目解析

Tn 等于前三项之和

算法思路

1. 状态表示：
   • 本题直接通过题目要求可知——>dp[i]表示第 i 个泰波那契数的值
2. 根据状态表示推导状态转移方程：dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
   • 依赖对象： dp[i] 依赖的是前三个状态
   • 如何依赖：前三个状态之和
3. 初始化：dp[0]=0 dp[1]=dp[2]=1
4. 填表顺序：从左向右
5. 返回值：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 表的时候，每次计算只需要前三个值，再前面的值都没用，所占的空间也就浪费了，这时候就可以用滚动数组

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

1. 初始化
   • 保证填表的时候不越界
   • 初始化前两个位置
2. 填表顺序
   • 从左向右（从左向右推）
3. 返回值
   • 返回 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])

1. 初始化

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

1. 填表顺序
   • 从右往左
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]);  
}