[アルゴリズム学習]白駿11726

7177 ワード
algorithm テキストリンク
質問元:https://www.acmicpc.net/problem/11726

質問へのアクセス
2 XNタイリング問題は動的プログラミングアルゴリズムの1つの問題であり,上から下へと下から上への解法がある.この問題はbottom-up方式で解決された.
(bottom-upは点火式を使用しています.)
n=1の場合、タイルを敷くことができる数は1種類あります
n=2の場合、タイルを敷くことができる数は2種類あります.
n=3の場合、タイルを敷くことができる数は3種類あります.
n=4の場合、タイルを敷くことができる数は5種類あります
すなわち、nが1又は2を除いて剥がすタイルの数は、(n−1)のタイルの数+(n−2)のタイルの数である.
コードとして記述すると、次のようになります.
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_11726 {
    static int[] dt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        dt = new int[1001];
        System.out.println(dp(N));
    }
    public static int dp(int N){
        if(dt[N] != 0) return dt[N];
        if(N == 1) return 1;
        if(N == 2) return 2;
        return dt[N] = (dp(N-1) + dp(N-2)) % 10007;
    }
}
This Month What I Learned 10
ASP.NET MVC 5学習ノートのActionパラメータモデルバインド基本手順