[白俊]9095号1.2.3プラス号

1075 ワード
ps テキストリンク

問題とI/O



質問へのアクセス


この問題を見て,動的プログラミングを利用することが分かった.
4を表すすべての方法を以下に示します.

ここから,4は3を表す方法と2を表す方法と1を表す方法を加えることで指数を求めることができる.
これを正規化し,a−1,a−2,a−3の指数を加えるとaの指数を求めることができる.

インプリメンテーションコード

import java.io.*;

public class Main {
  static int dp[];

  static int cal(int a){
    if(a == 0 || a == 1) {
      return 1;
    } else if(a == 2) {
      return 2;
    } else if(dp[a] > 0) {
      return dp[a];
    } else {
      dp[a] = cal(a-1) + cal(a-2) + cal(a-3);
      return dp[a];
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    dp = new int[12];

    for(int i = 0; i < T; i++){
      int n = Integer.parseInt(br.readLine());
      System.out.println(cal(n));
    }
  }
}
コーディングとデコード
[Javascript]Closureによるデータ操作とパッケージング