LC.1137. N-th Tribonacci Number – N次泰波那契数 常数空间复杂度的解法

背景与要求:
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.
特里波那契数列 Tn 的定义如下：
对于 n >= 0，T0 = 0, T1 = 1, T2 = 1, 并且Tn+3 = Tn + Tn+1 + Tn+2。
给定 n，返回 Tn 的值。

为了尽量减少时间复杂度，可以使用数组仅保留计算需要的3个数字，使用取模来获取当前计算位置，使得空间复杂度是O(1)，即常数级别的空间复杂度。Java实现如下:

class Solution {
    public int tribonacci(int n) {
        if(n==0) return 0;
        int[] t={0,1,1};
        int now=3;
        while(now <= n){
            t[now%3] = t[now%3] + t[(now+1)%3] + t[(now+2)%3];
            now++;
        }
        return t[--now % 3];
    }
}

其中，t[now%3]可以获得当前进行计算的位置。每次循环结尾now自增，因此返回结果时，使用now自减后的值。
当n>=3的时候，逻辑易于理解。
当n==2时，now==3并且now>n，不满足循环条件，直接执行返回操作，通过now自减后模3，返回的是t[2]==1，符合要求。
当n==1时，now同样大于n，不进入循环，返回的也是t[2]==1，符合要求。
当n==0时，只能直接返回0.
此代码空间复杂度为O(1)，时间复杂度仍需要O(n)。

同时用到了Dynamic Programming和Memoization的思想。
动态规划(Dynamic Programming)用于解决一些具有重叠子问题和最优子结构性质的问题。它的基本思想是将原问题分解为若干个子问题，先求解子问题，然后将子问题的解组合起来得到原问题的解。动态规划算法通常使用递推的方式来求解子问题，因此也被称为动态递推算法。
记忆化(Memoization)(memoization为计算机科学术语，与memorization不同，类比memoize与memorize)是一种优化技术，用于减少重复计算。它的基本思想是将计算过的结果缓存起来，以便在后续的计算中直接使用。Memoization 通常用于优化递归算法，可以将递归算法的时间复杂度从指数级别降低到多项式级别。