题解 | 牛牛学数列6

import java.util.*;
public class Main{
    public static int[] flag = new int[25];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(Main.dfs(n));
    }
    public static int dfs(int n){
        if(flag[n]!=0)return flag[n];//备忘录
        if(n==1){
            Main.flag[1] = 0;
            return 0;
        }
        else if(n==2||n==3){
            Main.flag[2] = 1;
            Main.flag[3] = 1;
            return 1;
        }
        int res = dfs(n-3)+2*dfs(n-2)+dfs(n-1);
        flag[n] = res;
        return res;
    }
}