白駿11726号です.
https://www.acmicpc.net/problem/11726

質問する

2×nサイズ1の矩形×2, 2×タイルで充填する方法の数を求めるプログラムを作成してください.
下図2×5長方形を充填する方法の一例.

入力

最初の行はnです.(1 ≤ n ≤ 1,000)

しゅつりょく

1行目2×n矩形を充填する方法数を10007で割った後、残りを出力する.

入力例

2

9

サンプル出力

2

55

考える

動的計画法では,前の問題1,2,3プラス記号とほぼ90%以上の類似度問題がある.
動的計画法の概念定義は良い問題だと思います.
以前解を解いたときは動的計画法を少し知っていたが,今では記憶法と動的計画法を少し知っている.
ここで問題をよく理解すると、実は1と2の組み合わせを簡単に使っただけです.
nが1のときは1です.
二は二
三銀.
4=5
ここで現れる規則はn=(n−1+n−2)である.
私たちはこの繰り返しのルールで答えを見つけることができます.
そして、この問題で注意しなければならないのは、最後に
矩形を塗りつぶす方法数を10007で割った後、残りを出力します.
10007の残金を忘れてはいけない.

アクション

		int n = Integer.parseInt(br.readLine());
		memoization = new int[1001];

		memoization[1] = 1;
		memoization[2] = 2;
		memoization[3] = 3;
		memoization[4] = 5;

まず、テストケースnの値を作成します.
前述したように、1と2の組み合わせであるため、1と2の値はmemoization配列に配置される.
ここには3と4しか置いていません.他の人は入れなくても大丈夫です.
次にdp()メソッドを実行して値を検索します

	static void dp(int num) {

		for(int i=4; i<=num; i++) {
			if(memoization[i] == 0) {

				memoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;				
			}
		}

	} // End of result

dp関数は、指定されたルールを繰り返し実行し、値をmemoization配列に格納します.
私たちが探している値numは、以前の配列と以前の配列の値の和です.
つまりmemoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;こうなります.
ここでポイント
私が最後に結果を出力したのはSystemでしたoutは%10007を貼り付け、残りの値を追加しました.
もともとmemoization配列に格納する場合は、10007で割った値を入れる必要があります.

コード#コード#

import java.io.*;

public class Main {
	static int memoization[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		memoization = new int[1001];

		memoization[1] = 1;
		memoization[2] = 2;
		memoization[3] = 3;
		memoization[4] = 5;

		dp(n);

		System.out.println(memoization[n]);
	} // End of main

	static void dp(int num) {

		for(int i=4; i<=num; i++) {
			if(memoization[i] == 0) {

				memoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;				
			}
		}

	} // End of result
} // End of class