动态规划专训1——泰波那契数列模型

这篇具有很好参考价值的文章主要介绍了动态规划专训1——泰波那契数列模型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划的思想:将一个问题分隔为若干个子问题,完成子问题得到结构再得到最终的答案

动态规划往往解题步骤固定,分为以下几步

1.找出状态表示

2.完成状态转移方程

3.初始化

4.填表顺序

5.返回值

后面三步偏重细节,二解题的核心就在于前两步,所以要想练好动态规划,大量的练习,见识更多的题型无疑是很重要的,下面我们开始今天的练习

1.第N个泰波那契数

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下: 

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

给你整数 n,请返回第 n 个泰波那契数 Tn 的值

这道题目很简单,旨在让我们熟悉动态规划的解题步骤,下面我们展开分析

1.状态表示:用dp[ i ]表示第 i 个泰波那契数

2.状态转移方程:dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ]

3.初始化:dp[0] = 0; dp[1] = 1; dp[2] = 1

4.填表顺序:从左往右依次填

5.返回值:dp[n]

当然我们要注意边缘数据的特殊处理,不然会出现越界的情况

class Solution {
public:
    int tribonacci(int n) 
    {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值

        //边缘数据处理
        if(n == 0 || n == 1) return n;
        if(n == 2) return 1;

        vector<int> dp(n + 1);
        dp[0] = 0; dp[1] = 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]; 
    }
};

这是ac代码

2.三步问题

面试题 08.01. 三步问题

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

1.状态表示:用dp[ i ]表示上到第i个台阶的可能方式

2.状态转移方程:dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ]

3.初始化:dp[0] = 0; dp[1] = 1; dp[2] = 1

4.填表顺序:从左往右依次填

5.返回值:dp[n]

这里要注意数据的处理,因为数据很大,每一次相加之后都要对题给数据取模

class Solution {
public:
    int waysToStep(int n) 
    {
        const int MOD = 1e9 + 7;
        if(n == 1 || n == 2) return n;

        vector<int> dp(n + 1);
        dp[0] = 1; dp[1] = 1; dp[2] = 2;
        for(int i = 3; i <= n; ++i)
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + + dp[i - 3]) % MOD; 

        return dp[n]; 
    }
};

这是ac代码

3.使用最小花费爬楼梯

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

数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当爬上一个阶梯都要花费对应的体力值,一旦支付了相应的体力值,就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯

1.状态表示:用dp[ i ]表示上到第i个阶梯需要的最小费用

2.状态转移方程:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

3.初始化:dp[0] = 0; dp[1] = 0;

4.填表顺序:从左往右依次填

5.返回值:dp[n]

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        
        vector<int> dp(n + 1);
        dp[0] = 0; dp[1] = 0;
        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];
    }
};

这是ac代码

4.解码方法

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法

1.状态表示:用dp[ i ]表示上到第i - 1个字母最大解码方法

2.状态转移方程:dp[i] = dp[i - 1] + dp[i - 2](要判断是否存在该情况)

3.初始化:dp[0] = 1; dp[1] = s[0] != '0';

4.填表顺序:从左往右依次填

5.返回值:dp[n]

class Solution {
public:
    int numDecodings(string s) 
    {
        int n = s.size();

        vector<int> dp(n + 1);
        dp[0] = 1; 
        dp[1] = s[0] != '0';
        for(int i = 2; i <= n; ++i)
        {
            if(s[i - 1] != '0') dp[i] += dp[i - 1];
            int num = (s[i - 2] -'0') * 10 + s[i - 1] - '0';
            if(num >= 10 && num <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
};

这是ac代码

新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!文章来源地址https://www.toymoban.com/news/detail-861748.html

到了这里,关于动态规划专训1——泰波那契数列模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法优选】 动态规划之斐波那契数列模型

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契

    2024年02月05日
    浏览(20)
  • 【动态规划】:泰波那契模型_解码方法

    朋友们、伙计们,我们又见面了,本专栏是关于各种算法的解析,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 C + + 专 栏   :C++ Linux 专 栏  :Linux 目录

    2024年02月19日
    浏览(9)
  • 【动态规划】斐波那契数列模型

    冻龟算法系列之斐波那契数列模型 动态规划(英语:Dynamic programming,简称 DP) ,是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质

    2024年02月09日
    浏览(32)
  • 【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月11日
    浏览(18)
  • 动态规划入门:斐波那契数列模型以及多状态(C++)

        动态规划(Dynamic programming,简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段,并通过保存中间结果来避免重复计算,从而提高效率。 动态规划的解题步骤一般分为以下几步: 思考状态表示,创建dp表(重点) 分析出状态转移方程(重点) 初始化 确定

    2024年02月11日
    浏览(16)
  • 【动态规划】是泰波那契数,不是斐波那契数

    Problem: 1137. 第 N 个泰波那契数 首先我们来解读一下本题的意思🔍 相信读者在看到【泰波那契数】的时候,不禁会联想到【斐波那契数】,它们呢是一对孪生兄弟,这个 泰波那契数 相当于是 斐波那契数 的加强版 我们首先可以来看到这个递推公式 Tn+3 = Tn + Tn+1 + Tn+2 ,读者可

    2024年02月08日
    浏览(14)
  • Java【动态规划】斐波那契数列模型, 图文思路详解 + 代码实现

    本篇总结动态规划中的 斐波那契数列模型 的解法和思路 按照以下流程进行分析题目和代码编写 思路分析步骤 代码编写步骤 1, 状态表示 1, 构造 dp 表 2, 状态转移方程 2, 初始化+边界处理 3, 初始化 3, 填表(抄状态转移方程) 4, 填表顺序 4, 返回结果 5, 返回值 / OJ链接 题目分析

    2024年02月08日
    浏览(21)
  • 【动态规划专栏】专题一:斐波那契数列模型--------2.三步问题

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月21日
    浏览(15)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(15)
  • 【学会动态规划】第 N 个泰波那契数(1)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 4. 空间优化 写在最后 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:1137. 第 N 个泰波那

    2024年02月15日
    浏览(24)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包