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

文章目录

• 模板
  • 算法原理
  • 代码编写
• 1. 第 N 个泰波那契数
  • 题目解析
  • 算法思路
  • 代码编写
  • 空间优化
• 2. 三步问题
  • 题目解析
  • 算法原理
  • 代码编写
• 3 . 使用最小花费爬楼梯
  • 题目解析
  • 算法原理
    • 解法一
    • 解法二
  • 代码编写

模板

算法原理

• 做动态规划的题目，一般会先创建一个一维数组 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 */publicinttribonacci(int n){//1. 创建 dp表 int[] dp =newint[n +1];//处理一下边界情况 if(n ==0)return0;if(n ==1|| n ==2)return1;//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 */publicinttribonacci2(int n){//处理一下边界情况 if(n ==0)return0;if(n ==1|| n ==2)return1;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]

代码编写

publicintwaysToStep(int n){int MOD =(int)1e9+7;//处理边界情况 if(n ==1|| n ==2)return n;if(n ==3)return4;int[] dp =newint[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]))

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

代码编写

解法一：

publicintminCostClimbingStairs(int[] cost){int n = cost.length;int[] dp =newint[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];}

解法二：

publicintminCostClimbingStairs2(int[] cost){int n = cost.length;int[] dp =newint[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];}returnMath.min(dp[0],dp[1]);}