【leetcode】1137. 第 N 个泰波那契数

今天是学习动归的第一天，先来一道简单题练练手吧！

1.题目

leetcode 1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

需要注意的是，这里的不是我们常用的斐波那契数列，哪个是 Tn = Tn-1 + Tn-2，而这里是三个；

2.动归解法

动态递归的思路是需要找到一个递归方程，本题中的递归方程已经给出来了。但是需要注意的是，当n小于3的时候，这个递归方程是不可用的（因为我们没有办法计算T_负数的值）

2.1 解法1-递归

如下是我的第一个解法，通过递归函数计算数值，并提前写入0、1、2这三个数值到数组里面。

如果数组里面有值，直接取出来，如果没有值，在计算了之后再赋值到数组里面。这样就能保证在整个递归流程中，相同下标处的数据只会被计算一次（不这么做会超时）

#define DEF -1 //默认值
    // 直接用递归会超时
    // 想法是将数据存到vector里面，避免针对某一个数的二次递归运算
    long long fib(int n,vector<int>& _map){
        if(_map[n] != DEF){
            return _map[n];
        }
        long long ans = fib(n-1,_map) + fib(n-2,_map)+fib(n-3,_map);
        _map[n] = ans;
        return ans;
    }

    int tribonacci(int n) {
        vector<int> _map(40,DEF);
        _map[0] = 0;
        _map[1] = 1;
        _map[2] = 1;
        // 初始化并传引用给递归函数
        return fib(n,_map);
    }

使用该方法的通过率如图

2.2 方法2-迭代

还是相同的思路，只不过这次我们不用递归，而是用迭代来计算出数组里面对应下标的值，最后再返回给用户

int tribonacci(int n) {
    if(n<=1){
        return n;
    }
    vector<int> _map(n+1,DEF);
    _map[0] = 0;
    _map[1] = 1;
    _map[2] = 1;
    for(int i=3;i<_map.size();i++){
        _map[i] = _map[i-3] +_map[i-2]+_map[i-1];
    }

    return _map[n];
}

该办法的通过率如图，时间复杂度和空间复杂度都是O(N)

2.3 迭代+变量

既然在计算的时候我们只需要用到当前数据和该数据之前的3个变量，所以我们完全可以用固定的几个变量来实现这个操作，每次计算之后，都对变量进行一次轮换就ok了，官方的题解就是这么操作的

int tribonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n <= 2) {
        return 1;
    }
    int p = 0, q = 0, r = 1, s = 1;
    for (int i = 3; i <= n; ++i) {
        p = q;
        q = r;
        r = s;
        s = p + q + r;
    }
    return s;
}

这样操作，时间复杂度还是O(N)，但是空间复杂度就降到O(1)了！

3.矩阵计算

如果不用递归，还可以用矩阵乘法运算，该方法的时间复杂度是O(LogN)

https://leetcode.cn/problems/n-th-tribonacci-number/solutions/921898/di-n-ge-tai-bo-na-qi-shu-by-leetcode-sol-kn16/

奈何本人线代知识忘记了，完全看不懂

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        vector<vector<long>> q = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
        vector<vector<long>> res = pow(q, n);
        return res[0][2];
    }

    vector<vector<long>> pow(vector<vector<long>>& a, long n) {
        vector<vector<long>> ret = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    vector<vector<long>> multiply(vector<vector<long>>& a, vector<vector<long>>& b) {
        vector<vector<long>> c(3, vector<long>(3));
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
            }
        }
        return c;
    }
};