[伯俊]9095-1,2,3加号(java)

質問する

整数4を1、2、3の和と表す方法は全部で7種類ある.和を表すときは1つ以上の数を使います.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.

入力

第1行は、試験例の個数Tを与える.各試験例は1行からなり、整数nが与えられる.nは正数で11未満である.

しゅつりょく

各試験例は、nが1,2,3の和を表す方法数を出力する.

入力例

3
4
7
10

サンプル出力

7
44
274

コード#コード#

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] dp = new int[n + 1];

            dp[1] = 1;
            for (int j = 2; j <= n; j++) {
                if (j >= 4) {
                    dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
                } else if (j == 2) {
                    dp[j] = dp[j - 1] + 1;
                } else if (j == 3) {
                    dp[j] = dp[j - 1] + dp[j - 2] + 1;
                }
            }
            bw.write(dp[n] + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

整理する

の順に書くと4以上からルールが見えてきます.