动态规划之斐波拉契数列模型

斐波拉契数列模型

  • 1. 第 N 个泰波那契数
  • 2. 三步问题（easy）
  • 3. 使⽤最⼩花费爬楼梯（easy）
  • 4. 解码⽅法（medium）

动态规划的介绍：
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

动态规划做题步骤通常如下：

  1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段（通常以某一个位置为结尾或者某一个位置为起点）。
  2. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
  3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，所以确定了决策，状态转移方程也就可以上来了。但事实上，写出状态转移方程是最困难的部分。
  4. 寻找边界条件：给出问题的边界条件，也就是最小的子问题。

1. 第 N 个泰波那契数

1.题⽬链接：第 N 个泰波那契数
2.题⽬描述：
泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
在这里插入图片描述
3.算法流程：

  1. 状态表示：
    这道题可以「根据题⽬的要求」直接定义出状态表⽰：
    dp[i] 表示：第 i 个泰波那契数的值。
  2. 状态转移⽅程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
  3. 初始化：
    从递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。
    因此我们需要在填表之前，将 0, 1, 2 位置的值初始化。根据题目可以知道如下初始化 dp[0] = 0, dp[1] = dp[2] = 1 。
  4. 填表顺序：从左往右。
  5. 返回值：应该返回 dp[n] 的值。

4.代码如下：

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

2. 三步问题（easy）

1.题目链接：三步问题
2.题目描述：三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:

输入：n = 3
输出：4
说明: 有四种走法

3.算法流程：

  1. 状态表示
    dp[i]表示：到达 i 位置时，⼀共有多少种⽅法。
  2. 状态转移方程
    以某一个位置为结尾进行讨论，比如这道以i位置结尾，可以走1步、2步或3步，那么i位置的方式等于i-1加i-2加i-3三种方式之和。如下：
    i. 上⼀步上⼀级台阶， dp[i] += dp[i - 1] ；
    ii. 上⼀步上两级台阶， dp[i] += dp[i - 2] ；
    iii. 上⼀步上三级台阶， dp[i] += dp[i - 3] ；
    综上所述， dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。
    需要注意的是，这道题⽬说，由于结果可能很大，需对结果取模。
    % MOD 是不可取的，因为可能两个数相加就会越界， n 取题⽬范围内最⼤值时，⽹站会报错 signed integer overflow 。
    对于这类需要取模的问题，我们每计算⼀次（两个数相加），都需要取⼀次模。
  3. 初始化
    从递推公式可以看出， dp[i] 在 i = 0, i = 1 以及 i = 2 的时候是没有办法进⾏推导的，因为 dp[-3] dp[-2] 或 dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前，将 1, 2, 3 位置的值初始化。
    根据题意， dp[1] = 1, dp[2] = 2, dp[3] = 4 。
  4. 填表顺序
    从左往右
  5. 返回值
    应该返回 dp[n] 的值。

4.代码如下：

class Solution
{
public:
    const int MOD = 1e9 + 7;
    int waysToStep(int n)
    {
        if (n == 1 || n == 2) 
        	return n;
        if (n == 3) 
        	return 4;
        vector<int> dp(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; //每相加MOD
        return dp[n];
    }
};

3. 使⽤最⼩花费爬楼梯（easy）

1.题目链接：使⽤最⼩花费爬楼梯
2.题目描述：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

  • 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  • 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  • 支付 1 ，向上爬一个台阶，到达楼梯顶部。
    总花费为 6 。

3.算法流程：

  1. 状态表示
    dp[i] 表⽰：到达 i 位置时的最⼩花费。（注意：到达 i 位置的时候， i 位置的钱不需要算上）
  2. 状态转移方程
    根据最近的⼀步，分情况讨论：
    ▪ 先到达 i - 1 的位置，然后⽀付 cost[i - 1] ，接下来⾛⼀步⾛到 i 位置：dp[i - 1] + csot[i - 1] ；
    ▪ 先到达 i - 2 的位置，然后⽀付 cost[i - 2] ，接下来⾛⼀步⾛到 i 位置：dp[i - 2] + csot[i - 2] 。
  3. 初始化
    从递推公式可以看出，需要先初始化 i = 0 ，以及 i = 1 位置的值。容易得到dp[0] = dp[1] = 0 ，因为不需要任何花费，就可以直接站在第 0 层和第 1 层上
  4. 填表顺序
    从左往右
  5. 返回值
    需要返回 dp[n] 位置的值。
    4.代码如下：
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i < n + 1; ++i)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

4. 解码⽅法（medium）

1.题目链接：解码⽅法
2.题目描述：
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
在这里插入图片描述

3.算法流程：

  1. 状态表示
    dp[i] 表⽰：字符串中 [0，i] 区间上，⼀共有多少种编码方法。
  2. 状态转移方程
    关于 i 位置的编码状况，我们可以分为下⾯两种情况：
    1.让 i 位置上的数单独解码成⼀个字母；
    i. 解码成功：当 i 位置上的数在 [1, 9] 之间的时候，说明 i 位置上的数是可以单独解码的，那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 1] 区间上的解码⽅法。因为 [0, i - 1] 区间上的所有解码结果，后⾯填上⼀个 i 位置解码后的字⺟就可以了。此时 dp[i] = dp[i - 1] ；
    ii. 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0, i] 区间上不存在解码⽅法。此时 dp[i] = 0 。
    2.让 i 位置上的数与 i - 1 位置上的数结合，解码成⼀个字母。
    i. 解码成功：当结合的数在 [10, 26] 之间的时候，说明 [i - 1, i] 两个位置是可以解码成功的，那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 2 ] 区间上的解码⽅法。此时 dp[i] = dp[i - 2] ；
    ii. 解码失败：当结合的数在 [0, 9] 和 [27 , 99] 之间的时候，说明两个位置结合后解码失败（这⾥⼀定要注意 00 01 02 03 04 … 这⼏种情况），那么此时 [0, i] 区间上的解码⽅法就不存在了。此时 dp[i] = 0 。
    综上所述： dp[i] 最终的结果应该是上⾯四种情况下，解码成功的两种的累加和，因此可以得到状态转移⽅程（ dp[i] 默认初始化为 0 ）：
    i. 当 s[i] 上的数在 [1, 9] 区间上时： dp[i] += dp[i - 1] ；
    ii. 当 s[i - 1] 与 s[i] 上的数结合后，在 [10, 26] 之间的时候： dp[i] += dp[i - 2] ；
    如果上述两个判断都不成⽴，说明没有解码⽅法， dp[i] 就是默认值 0 。
  3. 初始化
    初始化 dp[0] ：
    当 s[0] == ‘0’ 时，没有编码⽅法，结果 dp[0] = 0 ；
    当 s[0] != ‘0’ 时，能编码成功， dp[0] = 1
    初始化 dp[1] ：
    当 s[1] 在 [1，9] 之间时，能单独编码，此时 dp[1] += dp[0] （dp[1] 默认为 0 ）
    当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明在前两个字符中，⼜有⼀种编码⽅式，此时 dp[1] += 1
  4. 填表顺序
    从左往右
  5. 返回值
    应该返回 dp[n - 1] 的值，表⽰在 [0, n - 1] 区间上的编码⽅法。
    4.代码如下：
class Solution
{
public:
    int numDecodings(string s)
    {
        int n = s.size();
        vector<int> dp(n); // 创建⼀个 dp表
        // 初始化前两个位置
        dp[0] = s[0] != '0';
        if (n == 1) return dp[0]; // 处理边界情况
        if (s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
        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] <= '9' && s[i] >= '1') 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];
    }
};

以上为有关动态规划之斐波拉契数列模型的题目。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/74121.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Redis之缓存雪崩、缓存击穿、缓存穿透问题

Redis之缓存雪崩、缓存击穿、缓存穿透问题

文章目录 前言一、缓存雪崩1.1、原因分析2.2、常用解决方案 二、缓存击穿2.1、原因分析2.2、常用解决方案2.2.1、使用互斥锁2.2.2、逻辑过期方案2.3、方案对比 三、缓存穿透3.1、原因分析3.2、解决方案3.2.1、缓存空对象3.2.3、布隆过滤3.3、方案对比 总结 前言 本文谈谈Redis…
阅读更多...
基于DBN的伪测量配电网状态估计，DBN的详细原理

基于DBN的伪测量配电网状态估计，DBN的详细原理

目录 背影 DBN神经网络的原理 DBN神经网络的定义 受限玻尔兹曼机（RBM） DBN的伪测量配电网状态估计 基本结构 主要参数 数据 MATALB代码 结果图 展望 背影 DBN是一种深度学习神经网络，拥有提取特征，非监督学习的能力，是一种非常好的分类算法，本文将DBN算法伪测量配电网…
阅读更多...
Photoshop多图片与多窗口下排列操作方法

Photoshop多图片与多窗口下排列操作方法

首先&#xff0c;在Photoshop中打开6张图片&#xff0c;在“窗口”菜单下切换窗口排列状态&#xff1a; 在 “窗口”菜单下对窗口进行排列&#xff0c;分别呈现如下&#xff1a; &#xff08;一&#xff09;. 点击“窗口” -> “排列”->"全部垂直拼贴": &am…
阅读更多...
去掉数组中头部和尾部的0numpy.trim_zeros()

去掉数组中头部和尾部的0numpy.trim_zeros()

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 去掉数组中头部和尾部的0 numpy.trim_zeros() 选择题 以下说法错误的是? import numpy as np anp.array([0,0,1,2,3,4,0,0]) print("【显示】a:");print(a) print("【执行1】p…
阅读更多...
Intellij IDEA SBT依赖分析插件

Intellij IDEA SBT依赖分析插件

可分析模块和传递依赖 安装完插件后&#xff0c;由于IDEA BUG&#xff0c;会出现两个分析按钮&#xff0c;一个是gradle的&#xff0c;一般是后者是新安装的sbt。 选择需要分析的模块 只需要在project/plugins.sbt中添加代码&#xff0c;启动官方分析插件addDependencyTreeP…
阅读更多...
【前端 | CSS】align-items与align-content的区别

【前端 | CSS】align-items与align-content的区别

align-items 描述 CSS align-items 属性将所有直接子节点上的 align-self 值设置为一个组。align-self 属性设置项目在其包含块中在交叉轴方向上的对齐方式 align-items是针对每一个子项起作用&#xff0c;它的基本单位是每一个子项&#xff0c;在所有情况下都有效果&…
阅读更多...
postman入门基础 —— 接口测试流程

postman入门基础 —— 接口测试流程

一、编写接口测试计划 接口测试计划和功能测试计划目标一致&#xff0c;都是为了确认需求、确定测试环境、确定测试方法&#xff0c;为设计测试用例做准备&#xff0c;初步制定接口测试进度方案。一般来说&#xff0c;接口测试计划包括概述、测试资源、测试功能、测试重点、测试…
阅读更多...
C语言的动态分配空间C++的动态分配空间问题

C语言的动态分配空间C++的动态分配空间问题

动态分配空间 C&#xff1a;1、malloc 2、calloc C&#xff1a;new运算符 一 malloc malloc()&#xff1a; 这个函数用于分配一块指定大小的内存块&#xff0c;并返回一个指向该内存块的指针。语法如下&#xff1a; void* malloc(size_t size); 示例&#xff1a; int* ptr …
阅读更多...
Android Studio瀑布流实现

Android Studio瀑布流实现

效果&#xff1a; ImageDetail class package com.example.waterfallflow; import android.app.Activity; import android.content.Intent; import android.os.Bundle; import android.widget.ImageView;public class ImageDetail extends Activity{Overrideprotected void …
阅读更多...
web基础入门和php语言基础入门 二

web基础入门和php语言基础入门 二

web基础入门和php语言基础入门 二 MySQL入门-续MySQL之数据查询操作MySQL其他知识点 php语言基础入门认识PHPPHP的工作流程安装PHP环境认识一个PHP程序PHP基础知识点进入正题 PHP与WEB交互PHP与MySQL交互总结 MySQL入门-续 MySQL之数据查询操作 WHERE 子句&#xff0c;条件限…
阅读更多...
对话即数据分析，网易数帆ChatBI做到了

对话即数据分析，网易数帆ChatBI做到了

大数据产业创新服务媒体 ——聚焦数据 改变商业 在当今数字化快速发展的时代&#xff0c;数据已经成为业务经营与管理决策的核心驱要素。无论是跨国大企业还是新兴创业公司&#xff0c;正确、迅速地洞察数据已经变得至关重要。然而&#xff0c;传统的BI工具往往对用户有一定的…
阅读更多...
Destination Host Unreachable

Destination Host Unreachable

背景&#xff1a;物理机的IP地址是192.168.31.189&#xff0c;虚拟机的IP地址是192.168.194.130 物理机ping得通虚拟机 虚拟机ping得通外网 可是虚拟机ping不通物理机 1、报错信息 Destination Host Unreachable 2、原因 用route -n命令查看路由表发现192.168.194.0没有走网…
阅读更多...
读书笔记 |【项目思维与管理】➾ 项目成为一种生存方式

读书笔记 |【项目思维与管理】➾ 项目成为一种生存方式

读书笔记 |【项目思维与管理】➾ 项目成为一种生存方式 一、理解项目固有的挑战二、项目对企业的价值三、知识型企业的经营逻辑四、做项目管理的推进者 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 项目无处不在&#xff0c;项目已经成为…
阅读更多...
9.3.2.2网络原理(传输层TCP)

9.3.2.2网络原理(传输层TCP)

TCP全部细节参考RFC标准文档 一.TCP特点: 有连接,可靠传输,面向字节流,全双工. 二.TCP数据报: 1.端口号是传输层的重要概念. 2.TCP的报头是变长的(UDP是固定的8字节),大小存在4位首部长度中,用4个bit位(0~15)表示长度单位是4字节.(TCP报头最大长度是60字节,前面20字节是固定…
阅读更多...
Linux 复制进程fork

Linux 复制进程fork

一、父进程和子进程 当前的一个进程在fork的时候可以复制当前的进程产生一个进程&#xff0c;这时产生出来的这个进程就是子进程&#xff0c;被复制的进程叫做父进程。子进程会将环境变量从父进程继承过来&#xff0c;或者说被拷贝过来。父进程也会有它的父进程&#xff0c;一…
阅读更多...
四、Dubbo扩展点加载机制

四、Dubbo扩展点加载机制

四、Dubbo扩展点加载机制 4.1 加载机制概述 Dubbo良好的扩展性与框架中针对不同场景使用合适设计模式、加载机制密不可分 Dubbo几乎所有功能组件都是基于扩展机制&#xff08;SPI&#xff09;实现的 Dubbo SPI 没有直接使用 Java SPI&#xff0c;在它思想上进行改进&#xff…
阅读更多...
【自用】云服务器 使用 docker 搭建 HomeAssistant + MQTT 物联网平台

【自用】云服务器 使用 docker 搭建 HomeAssistant + MQTT 物联网平台

总览 1.搭建流程概述 2.准备工作 3.开始搭建&#xff01; 4.总结 如果想看 ESP32 或其他使用 MicroPython 编程的单片机如何连接到该云服务器&#xff0c;实现 HomeAssistant 控制 单片机的内容&#xff0c;请看我这篇博客的下一篇。 一、搭建流程概述 0.总体流程 我们需要…
阅读更多...
这四种订货系统不能选（二）：不能独立部署

这四种订货系统不能选（二）：不能独立部署

订货系统在传统批发贸易企业数字化转型中扮演着重要的角色。然而&#xff0c;有一种类型的订货系统并不适合选择&#xff0c;那就是无法独立部署的系统。 无法独立部署的订货系统意味着数据必须存放在软件厂商的服务器上。当我们选择这样的系统时&#xff0c;需要确保系统具备强…
阅读更多...
如何初始化Git仓库

如何初始化Git仓库

如何将目录初始化为Git仓库 一级目录二级目录三级目录 一、准备1、安装 gh2、登录 二、初始化 Git 仓库 一级目录 二级目录 三级目录 一、准备 ​ 在这里&#xff0c;我们需要借助一个非常好用的工具&#xff0c;大家也可以参照官方文档进行阅读&#xff0c;下面介绍常用的…
阅读更多...
从小白到大神之路之学习运维第79天-------Kubernetes网络组件详解

从小白到大神之路之学习运维第79天-------Kubernetes网络组件详解

第四阶段 时 间&#xff1a;2023年8月14日 参加人&#xff1a;全班人员 内 容&#xff1a; Kubernetes网络组件详解 目录 一、Kubernetes网络组件 &#xff08;一&#xff09;Flannel网络组件 &#xff08;二&#xff09;Calico 网络插件 &#xff08;1&#xff09;…
阅读更多...
最新文章

Copyright @ 2022~2023