首页 > 其他分享 >LeetCode 1137[第N个泰波那契数]

LeetCode 1137[第N个泰波那契数]

时间:2024-11-07 20:08:17浏览次数:1  
标签:契数 return 递归 int 个泰波 1137 tribonacci a1 a2

题目

链接

LeetCode 1137[第N个泰波那契数]

详情

实例

实例1

实例2

提示

题解

思路一[递归]

当 n 为 0, 1, 2 时,直接返回对应的值

当 n 大于 2 时,开始用 f(n+3) = f(n) + f(n+1) + f(n+2) 来递归求值

代码一[此代码在力扣会超出时间限制]

class Solution {
public:
    int tribonacci(int n) {
        
        if (0 == n)
            return 0;
        
        if ((1 == n) || (2 == n))
            return 1;

        return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
    }
};

思路二[循环代替递归]

当 n 为 0, 1, 2 时,直接返回对应的值

当 n 大于 2 时,开始用 f(n+3) = f(n) + f(n+1) + f(n+2) 来递归求值

由于递归是不停的复制粘贴,在运行时需要大量的时间,当 n 数值过大时,就会超过力扣官方限制的时间

因此此处采用循环代替递归的方法

此处的循环体为: f(n+3) = f(n) + f(n+1) + f(n+2) 

循环由 3 开始,由 n 结束,依次进入循环体求值,直到求出最后的 f(n) 的值并返回

代码二[此为成功代码]

class Solution {
public:
    int tribonacci(int n) {
        
        if (0 == n)
            return 0;
        
        if ((1 == n) || (2 == n))
            return 1;

        int a0 = 0, a1 = 1, a2 = 1;

        int iRet = 0;

        for (int i = 3; i < n + 1; i++)
        {
            iRet = a0 + a1 + a2;

            a0 = a1;
            a1 = a2;
            a2 = iRet;
        }

        return iRet;
    }
};

标签:契数,return,递归,int,个泰波,1137,tribonacci,a1,a2
From: https://www.cnblogs.com/EricsT/p/18533890

相关文章

  • 【动态规划之斐波那契数列模型】——累加递推型动态规划
    文章目录第N个泰波那契数列面试题08.01.三步问题使用最小花费爬楼梯解码问题第N个泰波那契数列解题思路:泰波那契数列的第N项定义为前面三项之和,即T0=0,T1=1,T2=1,从T3开始,每一项都等于前三项的和。要找到第N项,可以使用动态规划逐步求解每个值直到TN......
  • C# 小结实验:斐波那契数列 (7)
    代码//斐波那契数列publicclassFibonacciSequence{///<summary>///这是一个计算斐波那契数列方法。///</summary>///<paramname="index">第几个斐波那契数列</param>///<returns>第index个斐波那契数列值</returns>publicstat......
  • LeetCode_509. 斐波那契数_java
    1、题目509.斐波那契数https://leetcode.cn/problems/fibonacci-number/斐波那契数(通常用F(n)表示)形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2),其中n>1给定n,请......
  • 509_斐波那契数
    509_斐波那契数【问题描述】斐波那契数(通常用F(n)表示)形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2),其中n>1给定n,请计算F(n)。示例1:输入:n=2输出:1解释:F(2)......
  • 斐波拉契数列
    从0开始,如:0,1,1,2,3,5,8…#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//递归实现intFib(intx){if(x<=0){return0;}elseif(x>2){returnFib(x-1)+Fib(x-2);}elseif(x<=2&&......
  • 【算法】动态规划:从斐波那契数列到背包问题
    【算法】动态规划:从斐波那契数列到背包问题文章目录【算法】动态规划:从斐波那契数列到背包问题1.斐波那契数列2.爬楼梯3.零钱转换Python代码4.零钱兑换II5.组合数dp和排列数dp6.为什么动态规划的核心思想计算组合数的正确方法代码实现为什么先遍历硬币再遍历金额可以......
  • 代码随想录算法训练营 | 动态规划,509. 斐波那契数,70. 爬楼梯, 746. 使用最小花费爬楼梯
    动态规划:1.动态规划中每一个状态一定是由上一个状态推导出来的2.确定dp数组(dptable)以及下标的含义,确定递推公式dp,数组如何初始化,确定遍历顺序,举例推导dp数组;3.Debug:dp数组打印509.斐波那契数题目链接:509.斐波那契数文档讲解︰代码随想录(programmercarl.com)视频讲解︰斐波那......
  • Day 28 动态规划part01| LeetCode 509.斐波那契数,70.爬楼梯,746.使用最小花费爬楼梯
    理论基础包含题目类别:基础类(斐波那契、爬楼梯)、背包问题、打家劫舍、股票问题、子序列问题解题关键DP数组定义以及下标的含义递推公式DP数组如何初始化遍历顺序打印DP数组509.斐波那契数509.斐波那契数classSolution{publicintfib(intn){......
  • 一本通 1071:菲波那契数
    【题目描述】菲波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。给出一个正整数k,要求菲波那契数列中第k个数是多少。【输入】输入一行,包含一个正整数k。(1≤k≤46)【输出】输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小......
  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中......