【LeetCode】动态规划—第 N 个泰波那契数（附完整Python/C++代码）

前言

泰波那契数列是斐波那契数列的扩展版本。在斐波那契数列中，下一项是前两项之和，而在泰波那契数列中，下一项是前三项的和。具体的定义是:

• $T(\theta )=\theta$
• $T(1)=1$
• $T(2)=1$
• 对于 $n>=3,T(n)=T(n-1)+T(n-2)+T(n-3)$

问题要求的是，给定一个整数 $n$ ，返回第 $n$ 个泰波那契数。

题目描述

基本思路

1. 泰波那契数列的定义:

泰波那契数列是斐波那契数列的扩展版本。在斐波那契数列中，下一项是前两项之和，而在泰波那契数列中，下一项是前三项的和。具体的定义是:

• $T(\theta )=\theta$
• $T(1)=1$
• $T(2)=1$
• 对于 $n>=3,T(n)=T(n-1)+T(n-2)+T(n-3)$

问题要求的是，给定一个整数 $n$ ，返回第 $n$ 个泰波那契数。

2. 理解递推关系:

根据泰波那契数列的定义:

• 第 $\theta$ 项是 $\theta :T(\theta )=0$
• 第1项是 1： $\mathrm{T}(1)=1$
• 第 2 项是 $1:T(2)=1$
• 对于 $n>=3$, 每一项都是前三项的和: $T(n)=T(n-1)+T(n-2)+T(n-3)$

例如：

• $T(3)=T(2)+T(1)+T(\theta )=1+1+\theta =2$
• $T(4)=T(3)+T(2)+T(1)=2+1+1=4$
• $T(5)=T(4)+T(3)+T(2)=4+2+1=7$

3. 解决方法:

我们可以用动态规划来解决这个问题，通过递推公式一步步计算出结果。基本步䯅如下:

1. 初始条件：我们知道 $T(0)=0，T(1)=1，T(2)=1$ 。
2. 递推公式：对于 $n>=3$ 的情况， $T(n)=T(n-1)+T(n-2)+T(n-3)$ 。
3. 自底向上: 从 $n=3$ 开始，逐步计算到 $T(n)$ ，每一步只依赖前三个数值，所以我们可以优化空间复杂度。

4. 进一步优化:

在实现动态规划时，我们可以使用一个数组来保存每个泰波那契数，但实际上，计算第 $n$ 项时只需要知道前三项的值。因此，我们可以用三个变量来代替数组，从而优化空间复杂度为 $0(1)$ ，而时间复杂度仍然为 $O(n)$ 。

5. 小总结:

• 泰波那契数列的定义是： $T(n)=T(n-1)+T(n-2)+T(n-3)$ ，前面三项分别为 $T(0)=0，T(1)$ $=1,T(2)=1$ 。
• 我们可以通过动态规划自底向上计算，从 $T(3)$ 到 $T(n)$ ，每次使用前面的三个数值进行计算。
• 为了优化空间，我们可以使用常量空间的三个变量，避免使用数组。

以上就是泰波那契数问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def tribonacci(self, n: int) -> int:
        # 特殊情况：直接返回前三个数的结果
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        
        # 初始化前3个数：T(0), T(1), T(2)
        t0, t1, t2 = 0, 1, 1
        
        # 从第3项开始计算到第n项
        for i in range(3, n + 1):
            # 当前的泰波那契数是前三项的和
            current = t0 + t1 + t2
            # 更新前面的三个数
            t0, t1, t2 = t1, t2, current
        
        # 返回第n项
        return t2

Python 代码解释

1. Base Case: 对于 $n=0,1,2$ ，直接返回相应的结果。
2. 动态规划: 使用三个变量 $t0,t1,t2$ 分别表示 $T(n-3),T(n-2),T(n-1)$ ，在循环中逐步更新，直到计算到 $T(n)$ 。
3. 时间复杂度： $O(n)$ ，需要遍历计算到第 $n$ 项。
4. 空间复杂度: $O(1)$ ，只使用了三个变量存储前面的值。

C++代码实现

class Solution {
public:
    int tribonacci(int n) {
        // 特殊情况：直接返回前三个数的结果
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        // 初始化前3个数：T(0), T(1), T(2)
        int t0 = 0, t1 = 1, t2 = 1;
        
        // 从第3项开始计算到第n项
        for (int i = 3; i <= n; ++i) {
            // 当前的泰波那契数是前三项的和
            int current = t0 + t1 + t2;
            // 更新前面的三个数
            t0 = t1;
            t1 = t2;
            t2 = current;
        }
        
        // 返回第n项
        return t2;
    }
};

C++ 代码解释

1. Base Case: 如果 $n==0,1,2$ ，直接返回结果。
2. 动态规划: 使用三个变量 $t\theta ,t1,t2$ ，在每次循环中计算 $T(n)$ 并更新这三个变量。
3. 时间复杂度: $O(n)$, 遍历计算每一项。
4. 空间复杂度： $O(1)$ ，只使用了常量空间存储计算过程。

---

总结:

• Python 和 C++ 代码均使用动态规划和常量空间进行优化，保证了时间和空间的效率。
• 通过递推公式 $T(n)=T(n-1)+T(n-2)+T(n-3)$ ，可以快速从 $T(0),T(1),T(2)$ 逐步计算到第 $n$ 项。

原文地址：https://blog.csdn.net/AlbertDS/article/details/142457985

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！