1137, N-th Tribonacci Number

I Problem

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.

Related Topics

• Memoization
• Math
• Dynamic Programming

II Solution

Approach 1: Dynamic Programming

pub fn tribonacci(n: i32) -> i32 {
    //Self::dp_recur(n)
    Self::dp_iter(n)
}

/// Time Complexity: O(n)
/// Space Complexity: O(n)
fn dp_recur(n: i32) -> i32 {
    let len = if n < 3 { 3 } else { n as usize + 1 };
    let mut cache = vec![-1; len];
    (cache[0], cache[1], cache[2]) = (0, 1, 1);

    const RECUR: fn(&mut [i64], usize) -> i64 = |cache, n| {
        if cache[n] != -1 {
            return cache[n];
        }

        let sum = RECUR(cache, n - 1) + RECUR(cache, n - 2) + RECUR(cache, n - 3);
        cache[n] = sum;

        sum
    };

    RECUR(&mut cache, n as usize) as i32
}

/// Time Complexity: O(n)
/// Space Complexity: O(1)
fn dp_iter(n: i32) -> i32 {
    match n {
        0 => 0,
        1 | 2 => 1,
        _ => {
            let (mut t0, mut t1, mut t2, mut sum) = (0_i64, 0, 1, 1);

            for _ in 2..n {
                (t0, t1, t2) = (t1, t2, sum);
                sum = t0 + t1 + t2;
            }

            sum as i32
        }
    }
}

public int tribonacci(int n) {
    //return dpRecur(n);
    return dpIter(n);
}

BiFunction<long[], Integer, Long> recur = (cache, n) -> {
    if (cache[n] != -1) {
        return cache[n];
    }

    long sum = this.recur.apply(cache, n - 1) + this.recur.apply(cache, n - 2) + this.recur.apply(cache, n - 3);
    cache[n] = sum;

    return sum;
};

int dpRecur(int n) {
    int len = n < 3 ? 3 : n + 1;
    long[] cache = new long[len];
    for (int i = 0; i < len; i++) {
        if (i == 0) {
            cache[i] = 0;
        } else if (i == 1 || i == 2) {
            cache[i] = 1;
        } else {
            cache[i] = -1;
        }
    }

    return this.recur.apply(cache, n).intValue();
}

int dpIter(int n) {
    switch (n) {
        case 0 -> {
            return 0;
        }
        case 1, 2 -> {
            return 1;
        }
        default -> {
            long t0 = 0, t1 = 0, t2 = 1, sum = 1;

            for (int i = 2; i < n; i++) {
                t0 = t1;
                t1 = t2;
                t2 = sum;
                sum = t0 + t1 + t2;
            }

            return (int) sum;
        }
    }
}

func tribonacci(n int) int {
    //return dpRecur(n)
    return dpIter(n)
}

func dpRecur(n int) int {
    size := n + 1
    if size < 3 {
        size = 3
    }

    cache := make([]int, size)
    for i := range size {
        if i == 0 {
            cache[i] = 0
        } else if i == 1 || i == 2 {
            cache[i] = 1
        } else {
            cache[i] = -1
        }
    }    

    var recur func([]int, int) int
    recur = func(cache []int, n int) int {
        if cache[n] != -1 {
            return cache[n]
        }    
        sum := recur(cache, n-1) + recur(cache, n-2) + recur(cache, n-3)
        cache[n] = sum    
        return sum
    }

    return recur(cache, n)
}

func dpIter(n int) int {
    switch n {
    case 0:
        return 0
    case 1, 2:
        return 1
    default:
        t0, t1, t2, sum := 0, 0, 1, 1

        for i := 2; i < n; i++ {
        	t0, t1, t2 = t1, t2, sum
        	sum = t0 + t1 + t2
        }

        return sum
    }
}

Approach 2: Matrix Fast Power

/// Time Complexity: O(log(n))
/// Space Complexity: O(1)
pub fn tribonacci(n: i32) -> i32 {
    match n {
        0 => 0,
        1 | 2 => 1,
        _ => {
            let multiply = |a: &[Vec<i32>], b: &[Vec<i32>]| {
                let mut c = vec![vec![0; 3]; 3];
                for i in 0..3 {
                    for j in 0..3 {
                        c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
                    }
                }
                c
            };

            let mut m = vec![vec![1, 1, 1], vec![1, 0, 0], vec![0, 1, 0]];
            let mut pow = || {
                let mut ret = vec![vec![1, 0, 0], vec![0, 1, 0], vec![0, 0, 1]];
                while n > 0 {
                    if n & 1 == 1 {
                        ret = multiply(&ret, &m);
                    }
                    n >>= 1;
                    m = multiply(&m, &m);
                }
                ret
            };

            let res = pow();
            res[0][2]
        }
    }
}

public int tribonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n <= 2) {
        return 1;
    }

    BiFunction<int[][], int[][], int[][]> multiply = (a, b) -> {
        int[][] c = new int[3][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;
    };

    int[][] m = new int[][]{new int[]{1, 1, 1}, new int[]{1, 0, 0}, new int[]{0, 1, 0}};
    BiFunction<int[][], Integer, int[][]> pow = (_m, _n) -> {
        int[][] ret = new int[][]{new int[]{1, 0, 0}, new int[]{0, 1, 0}, new int[]{0, 0, 1}};
        while (_n > 0) {
            if ((_n & 1) == 1) {
                ret = multiply.apply(ret, _m);
            }
            _n >>= 1;
            _m = multiply.apply(_m, _m);
        }
        return ret;
    };

    int[][] res = pow.apply(m, n);
    return res[0][2];
}

func tribonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n <= 2 {
        return 1
    }    

    multiply := func(a, b *[][]int) [][]int {
        c := make([][]int, 3)
        c[0], c[1], c[2] = []int{0, 0, 0}, []int{0, 0, 0}, []int{0, 0, 0}    
        for i := range 3 {
            for j := range 3 {
            	c[i][j] = (*a)[i][0]*(*b)[0][j] + (*a)[i][1]*(*b)[1][j] + (*a)[i][2]*(*b)[2][j]
            }
        }    
        return c
    }

    m := make([][]int, 3)
    m[0], m[1], m[2] = []int{1, 1, 1}, []int{1, 0, 0}, []int{0, 1, 0}
    pow := func() [][]int {
        ret := make([][]int, 3)
        ret[0], ret[1], ret[2] = []int{1, 0, 0}, []int{0, 1, 0}, []int{0, 0, 1}    
        for n > 0 {
            if n&1 == 1 {
                ret = multiply(&ret, &m)
            }
            n >>= 1
            m = multiply(&m, &m)
        }    
        return ret
    }

    res := pow()
    return res[0][2]
}