力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题

贾蔷
• 阅读 29

力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题 一、题目分析

力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T0 =0, T1 =1, T2 =1, 且在n >= 0的条件下 Tn+3 = Tn + Tn+1 + Tn+2。,当n = 4时,T4 = T3 + T2 + T1 = 4。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们可以考虑从简单的情况入手,逐步推导到一般情况。

二、递归解法思路

递归是一种直观的解法。我们可以直接根据泰波那契数的定义来编写递归函数。当n为0时,返回0;当n为1或2时,返回1。对于n大于2的情况,我们通过递归调用函数自身来计算泰波那契数。即返回泰波那契(n - 1) + 泰波那契(n - 2) + 泰波那契(n - 3)。递归解法存在一个问题,就是会有大量的重复计算。,在计算泰波那契(5)时,泰波那契(3)会被计算多次。递归函数、重复计算、泰波那契数计算、边界条件这些方面需要我们仔细考虑。

三、动态规划解法思路

为了解决递归解法的重复计算问题,我们可以采用动态规划的方法。动态规划通常使用一个数组来保存已经计算过的结果。我们创建一个数组dp,其中dp[i]表示第i个泰波那契数。初始化dp[0] = 0,dp[1] = 1,dp[2] = 1。通过循环从3到n,依次计算dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。返回dp[n]即可。这种方法避免了重复计算,提高了效率。动态规划数组、初始化、循环计算、效率提升这些要点在动态规划解法中很重要。

四、C++代码实现递归解法

    if (n == 0) return 0; 
    if (n == 1 || n == 2) return 1; 
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
}

五、C++代码实现动态规划解法

    if (n == 0) return 0; 
    if (n == 1 || n == 2) return 1; 
    vector 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]; 
}

原文:https://www.dajuwangluo.cn/list/46.html

点赞
收藏
评论区
推荐文章
李志宽 李志宽
3年前
黑客赚钱的路子有多野?CTF逆向入门指南
1、背景在CTF比赛中,CTF逆向题目除了需要分析程序工作原理,还要根据分析结果进一步求出FLAG。逆向在解题赛制中单独占一类题型,同时也是PWN题的前置技能。在攻防赛制中常与PWN题结合。CTF逆向主要涉及到逆向分析和破解技巧,这也要求有较强的反汇编、反编译、加解密的功底。CTF中的逆向题目一般常见考点1、常见算法与数据结构。2、各种排序算法,树,
如何搞定力扣刷题?
好买网(www.goodmai.com)IT技术交易平台前言大家好,我是bigsai,好久不见!今天就给各位小伙伴分享我自己刷题力扣的一些小方法,不一定很有用但是可以参考,祝你更高效的变强!最近在一些群聊、私聊中遇到很多的一个问题就是:刷题,大家也都重视到算法刷题对冲击大厂的重要性,越来越多的人开始卷起来了!BA321C5AFE6864CE60465A0E7
Wesley13 Wesley13
3年前
java基础编程练习题
1、題目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?123456711235813这就是斐波那契数列(Fibonaccisequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Le
Stella981 Stella981
3年前
Python实现循环随机抽题
前几天有个同学问了我一个问题:现在班上共计有70名学生,题库中有20道题,每位同学随机抽5道题(不重复),该怎么用python实现这个功能?感兴趣的同学可以先不看下面的分析,试着自己实现一下这个功能。已经实现的同学或觉得有点问题的小伙伴,看看我的分析思路吧。1解题思路
Wesley13 Wesley13
3年前
Java面试不得不知的程序(二)
【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?斐波那契数列:前面相邻两项之和,构成了后一项通项公式注:此时a11,a21,ana(n1)a(n2)(n3,n∈N\)通项公式的推导斐波那契数列:1、1
Stella981 Stella981
3年前
Python递归函数、匿名函数、过滤函数
递归函数Python对递归的深度有限制,超过即会报错。所以一定一要注意跳出条件。斐波拉契数列一个数列,第一个数是1,第二个数也是1,从第三个数开始,每一个数是前两个数之和公式:f(1)1,f(2)1,f(3)f(1)f(2),...,f(n)f(n2)f(n1)
菜园前端 菜园前端
1年前
什么是动态规划?
原文链接:什么是动态规划?动态规划也是算法设计的一种方法/思想。它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。基础案例场景一斐波那契数列当前数等于前面两个数的和。定义子问题:f(n)f(n1)f(n2)
贾蔷 贾蔷
5天前
力扣145题:二叉树的后序遍历, 解题思路与C++实现
题目介绍力扣第145题要求实现一个函数,该函数接收一个二叉树的根节点,并返回该树的后序遍历结果。后序遍历是一种遍历二叉树的算法,其顺序为:先遍历左子树,是右子树,是根节点。解题思路分析解题时,我们可以使用递归或迭代的方法。递归方法较为直观,但可能导致栈溢出
贾蔷 贾蔷
1天前
力扣501题 解题思路和步骤 C++代码实现,力扣(leetcode)
问题背景及描述力扣501题要求我们找出在一个二叉搜索树(BST)中的众数。二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点,且小于其右子树中的任何节点。众数是指在BST中出现次数最多的值。解题思路分析解题的关键在于理解BST的性质以
贾蔷 贾蔷
1天前
力扣933题:队列的妙用:如何高效统计最近请求
题目重解:我们需要设计一个能统计最近3000毫秒内请求次数的系统。每当新的请求到来时,它会带有时间戳t,我们需要返回过去3000毫秒内(包括当前)发生的请求总数。这就像是在时间轴上维护一个滑动窗口,只关注最近3秒内的活动。解题思路解析:1.初始化:创建空队