[BaekJun](Java)9095-1,2,3プラス

質問リンク

https://www.acmicpc.net/problem/9095

問題を解く

以前に計算した値を用いて次の値を求める必要がある場合は,動的計画で近づける必要がある.問題のnの最大値は11なので、それより少し大きい12に並んでいます.
dp[0]留空は0であり、dp[1]=1、dp[2]=2、dp[3]=4が現れる.
nが1〜3の場合、簡単な算術で求め、dp[4]の場合、複数の場合の数を計算し、7を得る.
i>=4の場合、次の点火式が確立されます.
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

コード#コード#

import java.util.*;


public class Main {

    static int[] dp = new int[12];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = dp[1] * dp[1] + 1;//2
        dp[3] = dp[1] * dp[2] + dp[2] * dp[1] + 1 - 1; //4

        // dp[4] = 7
        //dp[5] = 13

        for (int i = 4; i <= 11; i++) {
            dp[i] += dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            System.out.println(dp[num]);
        }
    }
}