【动态规划-斐波那契数列模型】理解动态规划:斐波那契数列的递推模型

在这里插入图片描述

算法相关知识点可以通过点击以下链接进行学习一起加油!

动态规划是一种解决最优化问题的强大技术,通过将问题分解为子问题并逐步求解来实现高效计算。斐波那契数列是动态规划中经典的应用之一,其递推关系非常适合用动态规划进行优化。通过动态规划,我们不仅能避免重复计算,从而大幅提高计算效率,还能直观地理解递推模型在实际问题中的应用。本文将带你深入理解斐波那契数列的递推模型,展示如何利用动态规划来优化其计算过程,并探讨这一方法的实际价值与应用。

请添加图片描述

Alt

🌈个人主页:是店小二呀
🌈C/C++专栏:C语言\ C++
🌈初/高阶数据结构专栏: 初阶数据结构\ 高阶数据结构
🌈Linux专栏: Linux
🌈算法专栏:算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅 请添加图片描述

文章目录

  • 动态规划前言介绍
    • 1137第 N 个泰波那契数
    • 面试题 08.01. 三步问题
    • LCR 088. 使用最小花费爬楼梯
    • 91. 解码方法

动态规划前言介绍

动态规划(Dynamic Programming, DP)是一种解决最优化问题的方法,它将复杂问题拆解成多个简单的子问题,通过保存子问题的解来避免重复计算,从而提高计算效率。

动态规划适用于具有重叠子问题最优子结构的场景:

  1. 重叠子问题:问题可以被分解成相同的子问题,且子问题会重复计算。通过存储这些子问题的解,可以避免重复计算,节省时间。
  2. 最优子结构:问题的最优解可以通过其子问题的最优解来构建,即最优解是由子问题的最优解组合而成。

动态规划的基本思路】:

  1. 状态表示
  • 这一部分是指DP表里面的值所表达的含义。通常可以从以下三个角度来确定:
    1. 题目要求:从题目的要求来定义状态。
    2. 经验 + 题目要求:结合经验和题目要求确定状态。
    3. 分析问题的过程中,发现重复子问题:在分析问题时,可以发现哪些是重复的子问题,进而决定状态的定义。
  1. 状态转移方程
  • 状态转移方程描述了当前状态如何由前一个或多个状态推导出来。例如,dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3],这表示当前状态是由前几个状态的值组合而成的。
  1. 初始化
  • 设置初始状态,以确保在填表时不会越界。比如,对于斐波那契数列,dp[0]dp[1]可能需要提前设定为已知的初始值。
  1. 顺序计算
  • 在填充状态表时,必须保证填充当前状态时,所依赖的先前状态已经计算出来。这通常意味着需要按照一定的顺序(例如,从小到大)来计算状态。
  1. 返回值
  • 根据题目要求,返回最终的状态值。例如,如果我们计算的是最短路径、最大值或最优解,返回的是状态表中相应位置的值。

1137第 N 个泰波那契数

题目】:1137. 第 N 个泰波那契数

在这里插入图片描述

算法思路

这道题典型地使用动态规划(DP)来快速计算所需元素,流程如下:

  1. 创建 DP 表
  2. 初始化
  3. 填表
  4. 返回结果

代码实现

class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;if(n == 1 || n == 2) return 1;vector<int> dp(n + 1);dp[0] = 0;dp[1] = dp[2] = 1;for(int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2] + dp[ i- 3];return dp[n];}
};

优化方案】:滚动数组

在这里插入图片描述

class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;if(n == 1 || n == 2) return 1;vector<int> dp(n + 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;}
};

面试题 08.01. 三步问题

题目】:面试题 08.01. 三步问题

在这里插入图片描述

算法思路

面对未知的题目时,可以通过绘图寻找线索,帮助解决问题。例如,在这道题中,确定一个位置并列举所有可能情况,可以发现规律。比如,表示i位置前面三次的情况,所有可能组合加起来就是i位置的答案。

在这里插入图片描述

在这里插入图片描述

笔试中不需要使用滚动数组,也不用花时间去做空间优化。平时不必刻意练习这些,效果有限。

代码实现

class Solution {
public:int waysToStep(int n) {//1.创建dp表vector<int> dp(n + 2);if(n == 1 || n == 2) return n;if(n == 3) return 4;const int MOD = 1e9 + 7;//2.初始化dp[1] = 1;dp[2] = 2; dp[3] = 4;//3.填表for(int i = 4; i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2])%MOD + dp[i - 3])%MOD;return dp[n];}
};

细节问题

对于这类需要取模的问题,每次计算(如加法、乘法等)都要取一次模,以防止溢出,否则答案可能会错误


LCR 088. 使用最小花费爬楼梯

题目】:LCR 088. 使用最小花费爬楼梯

在这里插入图片描述

算法思路

解法一:

在这里插入图片描述

【小技巧】:通过之前或之后的状态推导出 dp[i] 的值。这类问题通常需要通过隐含或明确的递推关系来确定某个位置的数值。

代码实现

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();//1.创建dp表vector<int>dp (n + 1);//2.初始化dp[0] = dp[1] = 0;//3.填表for(int i = 2; i <= n; i++)dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[n];}
};

算法思路

解法二:

在这里插入图片描述
在这里插入图片描述

代码实现

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();//1.创建dp表vector<int>dp (n);//2.初始化dp[n - 1] = cost[n -1]; dp[n - 2] = cost[n - 2];//3.填表for(int i = n - 3; i >= 0; i--)dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];return min(dp[0], dp[1]);}
};

91. 解码方法

题目】:91. 解码方法

在这里插入图片描述

算法思路

在这里插入图片描述

我们使用 dp[i] 表示以位置 i 结尾时的解码方法总数。在分析位置 i 时,需要考虑两种情况:一种是单独解码 s[i],另一种是将 s[i-1]s[i] 结合解码。对于后者,必须满足 s[i-1]s[i] 形成一个有效的两位数(即在1到26之间,且没有前导零)。

因此,状态转移方程为:dp[i] = dp[i-1] + dp[i-2],但只有在满足解码条件时,才能进行累加。这样,我们能够从整体上分析解码的方案,而不是孤立地考虑每个子问题的解。

在这里插入图片描述

个人思考

通过整体思路来解决解码方案问题,结合这两张图片,可以更直观地理解解法。

为什么是相加,难道不会重复吗?其实,每个位置的解码方式是基于前面所有元素的解码结果,解法数量是通过添加‘单独解码’和‘双位解码’的方式得到的。因此,需要将之前的解码方案数相加,因为每个步骤都是缺一不可的。

在这里插入图片描述

在这里插入图片描述

代码实现

class Solution {
public:int numDecodings(string s) {              int n = s.size();//1.创建dp表vector<int> dp(n);//2.初始化dp[0] = s[0] != '0';if(n == 1) return dp[0];if(s[1] >= '1' && s[1] <= '9') dp[1] += dp[0];int t = (s[0] - '0') * 10 + (s[1] - '0');if(t >= 10 && t <= 26) dp[1] += 1;//3.填表操作for(int i = 2; i < n; i++){if(s[i] >= '1' && s[i] <= '9') dp[i] += dp[i - 1];int t = (s[i - 1] - '0') * 10 + (s[i] - '0');if(t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
};

在这里插入图片描述
快和小二一起踏上精彩的算法之旅!关注我,我们将一起破解算法奥秘,探索更多实用且有趣的知识,开启属于你的编程冒险!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/90702.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/90702.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信小程序 自定义带图片弹窗

1. 微信小程序 自定义带图片弹窗1.1. 实现思路使用官方组件实现图片模态弹窗。首先找到官方文档&#xff1a;​显示模态弹窗的API wx.showModal(OBJECT)wx.showModal参数介绍发现并没有设置图片的参数&#xff0c;但是这是一个API&#xff0c;但是组件呢&#xff1f;我并没有在…

私有化大模型架构解决方案构建指南

内容概要本指南旨在为企业提供私有化大模型架构解决方案的全面构建路径&#xff0c;帮助其在保障数据隐私的同时提升业务效率。我们将系统解析关键环节&#xff0c;包括安全部署策略设计、模型训练核心技术、持续优化机制构建以及知识管理实践路径。此外&#xff0c;指南还涵盖…

面试150 查找和最小的K对数字

思路1 超时法&#xff1a;通过两个循环记录三元组[num1,num2,num1num2]然后通过num1num2从小到大进行排序&#xff0c;然后返回前K个对数中的前两个数即可。 class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:if n…

vscode目录,右键菜单加入用VSCode打开文件和文件夹(快速解决)(含删除)(脚本)

1.创建文本文件 在桌面右键单击&#xff0c;选择“新建” > “文本文档”&#xff0c;将其命名为“vscode.txt”2.复制代码内容3.修改文件扩展名 右键单击“vscode.txt”文件&#xff0c;选择“重命名”&#xff0c;将文件扩展名从.txt改为.reg&#xff0c;使其成为“vscode…

Chart.js 柱形图详解

Chart.js 柱形图详解 引言 在数据可视化领域&#xff0c;柱形图是一种非常常见的图表类型&#xff0c;它能够直观地展示不同类别或组的数据之间的比较。Chart.js 是一个基于 HTML5 Canvas 的开源库&#xff0c;它提供了一系列的图表绘制功能&#xff0c;其中包括柱形图。本文将…

沉浸式文旅新玩法-基于4D GS技术的真人数字人赋能VR体验升级

线下沉浸式剧场与 LBE VR 相结合&#xff0c;会碰撞出什么样的火花&#xff1f;本次 PICO 视频、东方演艺集团与火山引擎一起&#xff0c;将沉浸式演出《只此周庄》的部分场景复刻到了 VR 世界&#xff0c;让用户在虚拟的古代周庄夜市里&#xff0c;体验了古老的故事以及精彩纷…

C程序内存布局详解

C程序内存布局详解 1. 内存布局概述 C程序在内存中分为以下几个主要区域&#xff08;从低地址到高地址&#xff09;&#xff1a; 代码段&#xff08;.text&#xff09;只读数据段&#xff08;.rodata&#xff09;初始化数据段&#xff08;.data&#xff09;未初始化数据段&…

新手向:Git下载全攻略

Git 的安装与重要性在现代软件开发中&#xff0c;版本控制是必不可少的工具&#xff0c;而 Git 是目前最流行的分布式版本控制系统。无论是个人开发者还是大型团队&#xff0c;Git 都能高效管理代码变更&#xff0c;确保项目历史清晰可追溯。安装 Git 是开发者入门的第一步&…

linux中如何清除history命令

写在前面 使用ssh远程连接客户端连接上linux后操作的命令多了&#xff0c;有时候需要清除对应的历史命令记录&#xff0c;可以通过下面几种方式实现。第一种方法 通过修改.bash_history文件 这是最简单直接的方法&#xff0c;但是只会影响当前用户的历史记录。执行以下命令即可…

PHP插件开发中的一个错误:JSON直接输出导致网站首页异常

问题描述 最近在使用步数统计插件&#xff08;WeFootStep&#xff09;时&#xff0c;发现网站首页完全变成了一段JSON数据&#xff0c;而不是正常的HTML页面。具体表现为首页显示如下内容&#xff1a; {"results":"<li><a href\"https:\/\/blog…

落霞归雁的思维框架:十大经典思维工具的源头活水

在当今复杂多变的世界中&#xff0c;思维框架成为了解决问题、优化决策和提升效率的重要工具。提到思维框架&#xff0c;人们往往会想到那些被广泛认可和应用的十大经典思维工具&#xff1a;金字塔原理、黄金圈法则、5W1H分析法、SWOT分析、SCQA模型、STAR法则、PDCA循环、六顶…

spring Could 高频面试题

一、基础概念Spring Cloud 的核心组件有哪些&#xff1f; 答案&#xff1a;Eureka/Nacos&#xff08;服务注册发现&#xff09;、Ribbon/LoadBalancer&#xff08;负载均衡&#xff09;、Feign/OpenFeign&#xff08;声明式HTTP客户端&#xff09;、Hystrix/Sentinel&#xff0…

从零开始的云计算生活——番外6,使用zabbix对中间件监控

目录 一.网络设备监控 1、GNS模拟器的使用 创建路由 创建交换机 2.构建网络 3.添加Cisco路由器的监控 二.中间件监控 1、MySQL数据库监控 1.1、拷贝自定义的监控脚本到指定目录 1.2、添加监控用户 1.3、重启zabbix-agent服务 1.4、在zabbix-server服务端测试数据 1…

haproxy七层均衡

一.haproxy的安装和服务信息1.1实验环境ip实验设备172.25.254.100haproxy172.25.254.10RS1172.25.254.20RS2172.25.254.111client1.2软件安装及配置haproxy主机上配置#下载#进入此文件进行编辑#关闭防火墙RS1主机上配置#下载#生成默认文件#重启#关闭防火墙RS2主机上配置#下载#生…

分类预测 | MATLAB实现CPO-SVM冠豪猪算法优化支持向量机分类预测

分类预测 | MATLAB实现CPO-SVM冠豪猪算法优化支持向量机分类预测 目录 分类预测 | MATLAB实现CPO-SVM冠豪猪算法优化支持向量机分类预测 分类效果 基本介绍 算法步骤 参数设定 运行环境 应用场景 程序设计 参考资料 分类效果 基本介绍 该MATLAB代码实现了基于冠豪猪优化算法(…

【MySQL 数据库】MySQL基本查询(第二节)

文章目录&#x1f4dd;Update&#x1f309; 将孙悟空同学的数学成绩变更为 80 分&#x1f309; 将曹孟德同学的数学成绩变更为60分&#xff0c;语文成绩变更为70分&#x1f309; 将总成绩倒数前三的3位同学的数学成绩加上30分&#x1f309;将所有同学的语文成绩更新为原来的2倍…

Axios 响应拦截器

1.定义&#xff1a;响应拦截器&#xff08;Response Interceptor&#xff09;是一个可以在 axios 接收到服务器响应后&#xff0c;响应数据交给 .then() 处理之前执行的函数。你可以用它来统一处理响应数据&#xff0c;进行错误处理&#xff0c;或者对返回的数据做格式化和转换…

k8s的nodeport和ingress

1.流量转发图targerport转发到实际的容器端口containerPort&#xff08;后端端口&#xff09;nodeportingress2.配置场景总结字段作用对象必填示例值何时配置containerPort容器否80需明确记录容器端口时&#xff08;推荐&#xff09;targetPortPod是80定义 Service 转发规则时p…

VLA:自动驾驶的“新大脑”?

&#x1f525; 什么是 VLA&#xff1f;为什么突然火了&#xff1f;在自动驾驶圈子里&#xff0c;最近一个词特别火&#xff1a;VLA。它不是某个新车的型号&#xff0c;也不是某家公司的新品牌&#xff0c;而是一种全新的智能架构&#xff0c;被称为“自动驾驶的大脑2.0”。&…

Linux操作系统之线程(八):信号量sem

前言&#xff1a;大家好啊&#xff0c;我们上一篇文章已经讲解了关于线程同步的一种办法&#xff1a;运用条件变量cond。今天&#xff0c;我们就来学习一下线程同步的另外一种方法&#xff0c;信号量&#xff01;&#xff01;信号量呢有System V 信号量与POSIX 信号量&#xff…