动态规划 之 斐波那契数列模型 算法专题

devtools/2024/11/7 22:08:28/

动态规划

分析:(五步)

  1. 状态表示

状态表示是什么?
dp表里面的值锁表示的含义

状态表示怎么来的?

  • 题目要求
  • 经验 + 题目要求
  • 线性状态表经验: 以i位置为结尾 以i位置为起点
  • 分析问题的过程中, 发现重复子问题
  1. 状态转移方程
    dp[i] 等于什么(一个公式)
    用之前或者之后的状态, 推导出dp[i]的值
  2. 初始化
    保证填表的时候不越界
  3. 填表顺序
    为了填写当前状态的时候, 所需要的状态已经计算过了
  4. 返回值
    题目要求 + 状态表示

编写代码: (四步)

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

优化: 处理边界问题以及初始化问题的技巧
如果初始化和填表的逻辑类似, 我们可以把初始化塞到填表逻辑中
做法:
dp多开一个空间, 将之前的dp表整体向后移动, 前面的一个位置称为虚拟节点
注意:
1.虚拟结点里面的值, 要保证是正确的 一般情况下设置为0, 但还是要具体分析
2.下标的映射关系

一.第n个泰波那契数

第n个泰波那契数

  1. 状态表示
    dp表 表示第n个泰波那契数
  2. 状态转移方程
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
  3. 初始化
    dp[0] = 0 dp[1] = 1 dp[2] = 1
  4. 填表顺序
    从左往右
  5. 返回值
    返回dp[n]
class Solution {public int tribonacci(int n) {//处理边界情况if(n == 0) return 0;if(n == 1 || n == 2) return 1;//1. 创建dp表int[] dp = new int[n + 1];//2. 初始化dp[0] = 0;dp[1] = dp[2] = 1;//3. 填表for(int i = 3; i <= n; i++){//状态转移方程dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];}//4. 确定返回值return dp[n];}
}

空间优化: 用滚动数组来实现(此题使用变量即可)

class Solution {public int tribonacci(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;}
}

二. 三步问题

三步问题

  1. 状态表示
    dp[i] 表示到达i位置时, 一共有多少种方法
  2. 状态转移方程
    以i位置的状态, 最近的一步来划分问题
    1.从 i - 1 到 i dp[i - 1]
    2.从 i - 2 到 i dp[i - 2]
    3.从 i - 3 到 i dp[i - 3]
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
  3. 初始化
    dp[1] = 1 dp[2] = 1 dp[3] = 4
  4. 填表顺序
    从左往右
  5. 返回值
    返回dp[n]
class Solution {public int waysToStep(int n) {// 1. 创建dp表// 2. 初始化// 3. 填表// 4. 确定返回值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 - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD;//每次做加法都有可能越界}return dp[n];}
}

三. 使用最小花费爬楼梯

使用最小花费爬楼梯
方法一: 以i位置结尾

  1. 状态表示
    dp[i] 表示到达i位置时, 最小花费
  2. 状态转移方程
    以i位置的状态, 最近的一步来划分问题
    1.先到达 i - 1 的位置, 然后支付cost[i - 1] 走一步 到 i dp[i - 1] + cost[i - 1]
    2.从先到达 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. 初始化
    dp[0] = dp[1] = 0
  2. 填表顺序
    从左往右
  3. 返回值
    返回dp[n]
class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 创建dp表// 2. 初始化// 3. 填表// 4. 确定返回值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];}
}

方法二: 以i位置开始

  1. 状态表示
    dp[i] 表示从i位置, 到达顶点的最小花费
  2. 状态转移方程
    以 i 位置的状态, 最近的一步来划分问题
    1.先支付cost[i] 走一步, 从 i 位置到达 i + 1 的位置, 然后到终点 dp[i + 1] + cost[i]
    2.先支付cost[i] 走两步, 从 i 位置到达 i + 2 的位置, 然后到终点 dp[i + 2] + cost[i]
  • dp[i] =min(dp[i + 1] + cost[i], dp[i + 2] + cost[i])
  1. 初始化
    dp[n] = cost[n], dp[n - 1] = cost[n - 1]
  2. 填表顺序
    从右往左
  3. 返回值
    返回min(dp[0], dp[1])
class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 创建dp表// 2. 初始化// 3. 填表// 4. 确定返回值int n = cost.length;int[] dp = new int[n];dp[n - 2] = cost[n - 2];dp[n - 1] = cost[n - 1];for(int i = n - 3; i >= 0; i--){dp[i] = Math.min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);}return Math.min(dp[0], dp[1]);}
}

四. 解码方法

解码方法

  1. 状态表示
    dp[i] 表示以 i 位置结尾, 解码方法的总数
  2. 状态转移方程

1.只解码 i 位置, 可以分成成功和失败两种情况
成功, s[i] 一定是>= 1 && <= 9, 说明从头开始到i位置, 都是可以正常解码的, 只需在解码成功的字符串后面加上一个字符, 那么dp[i] = dp[i - 1]
失败 说明不管前面解码是否成功, i位置失败了, 就不算解码成功, dp[i] = 0
2.解码 i 位置和 i - 1 位置, 也可以分成成功和失败两种情况
成功, s[i - 1] * 10 + s[i] 一定是>= 10 && <= 26, 说明从头开始到i位置, 都是可以正常解码的, 只需在解码成功的字符串(dp[i - 2])后面加上一个字符, 那么dp[i] = dp[i - 2]
失败 说明不管前面解码是否成功, i位置失败了, 就不算解码成功, dp[i] = 0

  • 成功条件: dp[i] =dp[i - 1] + dp[i - 2]
  1. 初始化
    dp[0] 一个字符的解码总数: 成功为1, 失败为0
    dp[1] 一个字符: 成功为1, 失败为0, 两个字符: 成功为1, 失败为0, 所以dp[1]可能为1, 2, 0
  2. 填表顺序
    从左往右
  3. 返回值
    返回dp[n - 1]
class Solution {public int numDecodings(String ss) {// 1. 创建dp表// 2. 初始化// 3. 填表// 4. 返回值char[] s = ss.toCharArray();int n = s.length;int[] dp = new int[n];//初始化dp[0]if (s[0] != '0')dp[0] += 1;//注意字符长度if (n == 1)return dp[0];//初始化dp[1]if (s[1] != '0' && s[0] != '0')dp[1] += 1;int t = (s[0] - '0') * 10 + s[1] - '0';if (t >= 10 && t <= 26)dp[1] += 1;//填表for (int i = 2; i < n; i++) {if (s[i] != '0')dp[i] += dp[i - 1];int tt = (s[i - 1] - '0') * 10 + s[i] - '0';if (tt >= 10 && tt <= 26)dp[i] += dp[i - 2];}return dp[n - 1];}
}

优化:
此题中, 虚拟节点dp[0]中的值, 应该为1
因为当dp[1]和dp[2]两个字符一起看的时候, 如果能映射成字符, 那么dp[2] = dp[2 - 2] = dp[0], 此时应该算作一个结果, 应该为1

class Solution {public int numDecodings(String ss) {// 1. 创建dp表// 2. 初始化// 3. 填表// 4. 返回值char[] s = ss.toCharArray();int n = s.length;int[] dp = new int[n + 1];// 初始化dp[0]dp[0] = 1;// 虚拟节点// 初始化dp[1]if (s[0] != '0')dp[1] = 1;// 填表for (int i = 2; i <= n; i++) {if (s[i - 1] != '0')dp[i] += dp[i - 1];int tt = (s[i - 2] - '0') * 10 + s[i - 1] - '0';if (tt >= 10 && tt <= 26)dp[i] += dp[i - 2];}return dp[n];}
}

http://www.ppmy.cn/devtools/132132.html

相关文章

Windows 命令提示符(cmd)中输入 mysql 并收到错误消息“MySQL不是内部或外部命令,也不是可运行的程序或批处理文件?

目录 背景: 过程&#xff1a; 1.找到MySQL安装的路径 2.编辑环境变量 3.打开cmd&#xff0c;输入mysql --version测试成功 总结: 背景: 很早之前安装了Mysql数据库&#xff0c;想查询一下当前安装的MySQL客户端的版本号&#xff0c;我在命令行界面输入mysql --verion命令回…

使用 Python 和 OpenCV 实现实时人脸识别

概述 人脸识别是一项重要的计算机视觉任务&#xff0c;广泛应用于安全监控、身份验证等领域。本文将详细介绍如何使用 Python 和 OpenCV 库实现实时人脸识别&#xff0c;并通过具体的代码示例来展示整个过程。 环境准备 在开始编写代码之前&#xff0c;确保已经安装了 OpenC…

《Vue3 报错》Uncaught TypeError: s.finally is not a function

解决方案&#xff1a; 新建文件 my-polyfill.js // 当浏览器环境不支持Promise.prototype.finally if (!Promise.prototype[finally]) {Promise.prototype[finally] function(callback) {let P this.constructor;return this.then(value > P.resolve(callback()).then(…

org.springframework.boot:type=Admin,name=SpringApplication异常

org.springframework.boot:typeAdmin,nameSpringApplication异常 问题&#xff1a;更换最新版本idea之后&#xff0c;启动springboot项目报错 javax.management.InstanceNotFoundException: org.springframework.boot:typeAdmin,nameSpringApplication idea自动默认的启动设…

如何调整电脑的背景色(黑色和白色切换)

1.切换谷歌浏览器里面内容的背景色 打开浏览器->右上角三个点->设置->外观->模式 中点击深色和浅色即可切换。 如果切换完之后并刷新发现有的网站还是没有变化&#xff0c;说明这个网站的背景色是依据电脑的背景色而变化的。也就是需要执行下面的第2个。 2.切换电…

SpringMVC的执行流程以及运行原理

文章目录 SpringMVC的执行流程以及运行原理一、引言二、SpringMVC核心组件与执行流程1、SpringMVC核心组件1.1、DispatcherServlet配置 2、SpringMVC执行流程 三、SpringMVC配置文件及注解四、总结 SpringMVC的执行流程以及运行原理 一、引言 SpringMVC作为Spring框架的核心模…

【笔记】变压器-热损耗-频响曲线推导 - 04 额定功率处损耗特性

0.最大的问题 - 散热 对变压器这类功率器件&#xff0c;最大的问题是散热的效率。因为传统的电路基板热导率并不高&#xff0c;几乎和良性导热材料有近乎两个数量级的导热差异&#xff0c;所以&#xff0c;会采用特殊的导热技术&#xff0c;把热量尽可能快地传导到散热片。 传…

STM32F103C8T6学习笔记2--LED流水灯与蜂鸣器

1、简要说明与电路图 LED灯与蜂鸣器都是GPIO的输出操作&#xff0c;给高低电平实现。GPIO操作也是后续操作的基础&#xff0c;没有什么难度&#xff0c;记不住寄存器没关系&#xff0c;只要把流程理清楚就可以了。 端口配置成推挽输出模式&#xff0c;高低电平均有驱动能力。 …