【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数

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

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

点击直接跳转到该题目

🍬题目描述

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

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

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

示例 1:

输入:n = 4
输出:4
解释
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2:

输入:n = 25
输出:1389537

🍦动态规划算法原理+题目解析。

这里要求的是第n个泰波那契数,泰波那契数不同于斐波那契数,两者区别如下:

斐波那契数列以0和1为初始值,每个数字是前两个数字的和,形成的数列是0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …。
泰波那契数列以0、1和1为初始值,每个数字是前三个数字的和,形成的数列是0, 1, 1, 2, 4, 7, 13, 24, 44, …。

说白了,第n个泰波那契数其实就是前面3项加起来的和。用一个公式来表示就是Tn = Tn-3 + Tn-2 + Tn-1

现在我们先来简单介绍一下什么是动态规划。

动态规划算法通过将问题分解成子问题,并利用子问题的解推导出更大规模问题的解,避免了重复计算,从而提高了算法的效率。

我们今后在练习动态规划的题目的时候,一般会按照如下几个步骤进行题目的分析、解答。请看:
步骤1(最重要).状态表示

状态表示是什么意思呢?我们要先建立一个dp表(一般是一个一维数组或者二维数组),状态表示其实就是dp表中每个位置的具体含义。
那我们应该如果来求取题目的状态表示呢?状态表示又是怎么来的?这里给出了3种方法,请看:
①根据题目要求,题目怎么要求的我们就怎么来
②(重点)根据自己的经验+题目要求
③分析问题的过程中,发现了重复的子问题

【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数

由于这个题目(第 N 个泰波那契数)比较简单,所以我们可以直接根据题目要求来得到题目的状态表示。在本题目中,dp表即dp[i]就表示第 N 个泰波那契数。

步骤2(最难):状态转移方程

我们先来看看官方是怎么定义状态转移方程的,请看:找到子问题之间的递推关系,即通过已知子问题的解推导出更大规模的子问题的解。
其实说简单一点,就是求dp[i]等于什么
在本题目中,dp[i]=d[i-3]+d[i-2]+dp[i-1]

步骤3:初始化

步骤3就是根据状态转移方程来填表,而且必须保证填表的时候不能越界
在本题目中,根据状态转移方程dp[i]=d[i-3]+d[i-2]+dp[i-1]来进行初始化,由于必须要保证不越界,所以根据题目要求,我们只需要初始化dp[0]=0、dp[1]=1、dp[2]=1

步骤4:填表顺序

为了填写当前状态的时候,所需要的状态已经计算过了。
这里举个例子,我们已经知道了dp[0]、dp[1]、dp[2]位置的状态,可以根据这三个位置的状态来填写dp[3]。但是我们如果想要知道dp[4]的话,我们就需要三个位置的状态(即dp[1]、dp[2]、dp[3]位置的状态)。

步骤5:返回值

由于这里dp[i]表示第i个泰波那契数,所以dp[n]就表示第n个泰波那契数。所以这里返回值很简单
,我们直接返回dp[i]就好了。

以上就是动态规划的几个基本的步骤。

🍰解题代码1

class Solution {
public:
    int tribonacci(int n) {

        //处理越界问题
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        //创建dp表
        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];
    }
};

🍔解题代码2(空间优化—滚动数组)

我们可以对本题进行一个空间优化,即利用滚动数组。
那这里是怎样一个空间优化呢?我们先来分析一下在哪里我们可以进行空间优化。

就比如说我们在求取dp[4]的值的时候需要用到dp[1]、dp[2]、dp[3]的值,而dp[0]的值是用不到的;
所以这里就造成了一部分空间的浪费。
在比如说,我们在求取dp[6]的值的时候需要用到dp[3]、dp[4]、dp[5]的值,而dp[0]、dp[1]、dp[2]的值是用不到的;所以这里一下子就造成了dp[0]、dp[1]、dp[2]所占空间的浪费。

【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数

需要注意的是,当我们在进行变量a、b、c的赋值操作的时候,必须从前往后赋值,而不能从后往前赋值。

总结:当我们一次求取dp[i]的时候,前面的某些状态如果可以舍去,仅仅使用中间有效的若干个状态,这种情况我们就可以使用滚动数组来解决问题。
下面来看解题代码,请看:

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;
    }
}

🍩总结

本文搭配题目主要讲解了动态规划的大体思路:

分析题目时主要有5个步骤,分别是状态表示、状态转移方程、初始化、顺序填表、返回值
写代码时主要有4个步骤:分别是创建dp表、初始化、填表、返回值,最后一定要处理边界问题(比如当n比较小的时候可能会造成越界)。

好了,以上就是本文的全部内容,希望可以帮到大家。
那就再见啦,友友们!!!

【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数文章来源地址https://www.toymoban.com/news/detail-515491.html

到了这里,关于【手撕算法|动态规划系列No.1】leetcode1137. 第 N 个泰波那契数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【手撕算法|动态规划系列No.2】leetcode面试题 08.01. 三步问题

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

    2024年02月12日
    浏览(64)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

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

    2024年02月12日
    浏览(43)
  • LeetCode第 N 个泰波那契数 (认识动态规划)

    链接: 第 N 个泰波那契数 编写代码 代码空间优化 一般像这种情况我们可以使用滚动数组的方式来解决空间的问题

    2024年02月15日
    浏览(39)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

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

    2024年02月16日
    浏览(49)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

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

    2024年02月07日
    浏览(49)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

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

    2024年02月08日
    浏览(45)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

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

    2024年02月07日
    浏览(46)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

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

    2024年02月06日
    浏览(44)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

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

    2024年02月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包