题解 | 牛牛学数列6

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 调用方法计算并输出结果
        System.out.println(calculateAn(n));
        scanner.close();
    }

    // 计算数列 An 的方法
    public static int calculateAn(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2 || n == 3) {
            return 1;
        } else {
            // 用于存储前面计算的结果，避免重复计算
            int[] dp = new int[n + 1];
            dp[1] = 0;
            dp[2] = 1;
            dp[3] = 1;
            for (int i = 4; i <= n; i++) {
                dp[i] = dp[i - 3] + 2 * dp[i - 2] + dp[i - 1];
            }
            return dp[n];
        }
    }
}