How to Compute the N-th Tribonacci Number using Iterative Dynami

  • 时间:2020-09-23 15:11:59
  • 分类:网络文摘
  • 阅读:87 次

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and
Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:
Input: n = 25
Output: 1389537

Constraints
0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 – 1.

A Tribonacci is very much similar to Fibonacci except that the Tribonacci is the sum of its previous 3 Tribonacci in the sequences.

Iterative Approach to compute the n-th Tribonacci

Like the Fibonacci, we can use three variables to iterate the process, at each iteration, we need to shift those three variables i.e. T(i), T(i+1) and T(i+2) respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int tribonacci(int n) {
        int t[3] = {0, 1, 1};
        if (n <= 2) return t[n];
        for (int i = 3; i <= n; ++ i) {
            int a = t[0] + t[1] + t[2];
            t[0] = t[1];
            t[1] = t[2];
            t[2] = a;
        }
        return t[2];
    }
};
class Solution {
public:
    int tribonacci(int n) {
        int t[3] = {0, 1, 1};
        if (n <= 2) return t[n];
        for (int i = 3; i <= n; ++ i) {
            int a = t[0] + t[1] + t[2];
            t[0] = t[1];
            t[1] = t[2];
            t[2] = a;
        }
        return t[2];
    }
};

The final answer is at T[2] – where it is the last Tribonacci number computed. The above takes O(N) time and O(1) constant space.

Dynamic Programming Algorithm to compute the n-th Tribonacci number

The Dynamic programming equation is actually already given already, thus we just have to implement it and store the intermediate values in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int tribonacci(int n) {
        vector<int> f(max(3, n + 1));
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        if (n <= 2) return f[n];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
        return f[n];
    }
};
class Solution {
public:
    int tribonacci(int n) {
        vector<int> f(max(3, n + 1));
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        if (n <= 2) return f[n];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
        return f[n];
    }
};

O(N) time and O(N) space. However given the problem statement saying that the n is maximum 37. Both time and space complexity is thus O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
亚洲联合卫视直播「高清」  香港TVB8直播「高清」  卫视体育台直播_星空卫视体育台直播观看「高清」  华娱卫视在线直播「高清」  新城财经台直播「高清」  香港本港台直播-亚洲电视本港台直播-atv直播「高清」  深度剖析:电脑打板的全过程-故障排查  如何高效管理你的电脑数据传输?技巧大揭秘-故障排查  Win11开始菜单怎么关闭最近使用文件显示  本港国际台直播「高清」 
评论列表
添加评论