【算法学习】第N个泰波那契数

2023-12-24 18:26:27

一、题目描述

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

二、解析题目

? ? ? ? 常规并且简单的动态规划题目,根据动规步骤一步步来即可。

? ? ? ? 动态规划的题围绕着dp表展开的。此题根据题目信息是一个线性的递推过程,一维dp表即可。

1.状态表示

? ? ? ? 对于状态,我的通俗理解是dp表中值的意义或者什么意思。因为我们是要求解第n个泰波那契数,那么dp[i]就表示是第i个泰波那契数的值了。

2.递推公式

? ? ? ? 根据题目,提取出关键信息:在 n >= 0?的条件下 Tn+3?= Tn?+ Tn+1?+ Tn+2

? ? ? ? 转换一下,可以得到:Tn = Tn-3 + Tn-2 + Tn - 1;(n >=3)。

? ? ? ? 这也是之后计算dp表每个值的递推公式。

3.初始化

? ? ? ? 初始化的目的是为了dp在填表过程中不会发生数组越界。因为n>=3,所以这里初始化我们需要给初始的三个值0、1、2赋值。(根据题目赋予的值为0、1、1)

4.填表顺序

? ? ? ? 需要从左到右依次填表。因为递推公式需要的是此下标的前三个下标对应值的累和。

5.返回值

? ? ? ? 返回值就是对应的dp[n]。

? ? ? ? 正常的dp题流程到此结束。分析上述算法,空间复杂度On(数组n+1的大小),时间复杂度On(迭代循环)。但是此题根据递推公式可以发现在计算某一状态值时,利用的只是前面三个状态的值,为此我们可以进行空间优化。

空间优化

? ? ? ? 我们可以利用滚动数组的思维方式进行空间优化。

? ? ? ? 在原本创建dp表的这一步,我们只需要替换为四个变量即可,前三个表示前三个状态,第四个表示现在我正在求的状态值,循环迭代的时候计算完当前状态值,前三个变量重新赋值即可,只需要保持时前三个状态的值。

? ? ? ? 这样,我们就可以把之前的On大小的空间优化为O1(只有变量的空间)。

三、代码参考

1.常规思路

class Solution {
public:
    int tribonacci(int n) {
        // 越界处理
        if (n == 0) return 0;
        if (n < 3) return 1;

        //1创建dp表
        vector<int> dp(n + 1);
        //2初始化
        dp[0] = 0, dp[1] = dp[2] = 1;
        //3填表
        for (int i = 3; i <= n; ++i)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};

2.空间优化思路

class Solution {
public:
    int tribonacci(int n) {
        // 越界处理
        if (n == 0) return 0;
        if (n < 3) return 1;

        // 优化空间
        // 滚动数组解决问题:仅仅需要前面的几种状态值
        // 1初始化
        int a, b, c, d;
        a = d = 0;
        b = c = 1;
        // 2循环迭代
        for (int i = 3; i <= n; ++i)
        {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }

        return d;
    }
};

文章来源:https://blog.csdn.net/weixin_61508423/article/details/135183675
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。