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

动态规划—#1137. 第 N 个泰波那契数

• 前言
• 题目描述
• 基本思路
  • 1. 泰波那契数列的定义:
  • 2. 理解递推关系:
  • 3. 解决方法:
  • 4. 进一步优化:
  • 5. 小总结:
• 代码实现
• • Python3代码实现
  • Python 代码解释
  • C++代码实现
  • C++ 代码解释
• 总结:

前言

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

• 对于

问题要求的是，给定一个整数

，返回第

个泰波那契数。

题目描述

在这里插入图片描述

基本思路

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

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

• 对于

问题要求的是，给定一个整数

，返回第

个泰波那契数。

2. 理解递推关系:

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

• 第

项是

• 第1项是 1：

• 第 2 项是

• 对于

, 每一项都是前三项的和:

例如：

3. 解决方法:

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

1. 初始条件：我们知道

。

1. 递推公式：对于

的情况，

。

1. 自底向上: 从

开始，逐步计算到

，每一步只依赖前三个数值，所以我们可以优化空间复杂度。

4. 进一步优化:

在实现动态规划时，我们可以使用一个数组来保存每个泰波那契数，但实际上，计算第

项时只需要知道前三项的值。因此，我们可以用三个变量来代替数组，从而优化空间复杂度为

，而时间复杂度仍然为

。

5. 小总结:

• 泰波那契数列的定义是：

，前面三项分别为

。

• 我们可以通过动态规划自底向上计算，从

到

，每次使用前面的三个数值进行计算。

• 为了优化空间，我们可以使用常量空间的三个变量，避免使用数组。

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

代码实现

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: 对于

，直接返回相应的结果。

1. 动态规划: 使用三个变量

分别表示

，在循环中逐步更新，直到计算到

。

1. 时间复杂度：

，需要遍历计算到第

项。

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: 如果

，直接返回结果。

1. 动态规划: 使用三个变量

，在每次循环中计算

并更新这三个变量。

1. 时间复杂度:

, 遍历计算每一项。

1. 空间复杂度：

，只使用了常量空间存储计算过程。

总结:

• Python 和 C++ 代码均使用动态规划和常量空间进行优化，保证了时间和空间的效率。
• 通过递推公式

，可以快速从

逐步计算到第

项。