トリボナッチ数列 一般化を使って問題を解く

トリボナッチ数列とは

最初の3つは 0, 1, 1 で、4つ目以降は"前3つを足したもの"
ex) 0 1 1 2 4 7 ...

コード java

class Solution {
    public int tribonacci(int n) {
        if(n ==0) return 0;
        if(n<3) return 1;
        int []array = new int [n+1];
        array[0]=0;
        array[1]=1;
        array[2]=1;
        
        for (int i=3; i <= n;i++){
            array[i]=array[i-1]+array[i-2]+array[i-3];
        }
        return array[n];
    }
}

実行時間:0ms
メモリー：40.38MB

forループの初期化部分を省略

class Solution {
    public int tribonacci(int n) {
        if(n ==0) return 0;
        if(n<3) return 1;
        int []array = new int [n+1];
        int i=3;
        array[0]=0;
        array[1]=1;
        array[2]=1;
        
        for (; i <= n;i++){
            array[i]=array[i-1]+array[i-2]+array[i-3];
        }
        return array[n];
    }
}

実行時間:0ms
メモリー：40.40MB

計算順番を変更

class Solution {
    public int tribonacci(int n) {
        if(n ==0) return 0;
        if(n<3) return 1;
        int []array = new int [n+1];
        int i=3;
        array[0]=0;
        array[1]=1;
        array[2]=1;
        
        for (; i <= n;i++){
            array[i]=array[i-3]+array[i-2]+array[i-1];
        }
        return array[n];
    }
}

実行時間:0ms
メモリー：40.00MB

結果

計算対象の要素が最も小さい箇所から計算することにより、消費メモリーを抑えることができる