アルゴリズム学習6週目[ダイナミックプログラミング]2

白駿11726号問題
2 x nタイル

bottom-up方式

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%10007;
        }
        System.out.println(dp[n]%10007);
    }
}

dp配列の1番と2番はそれぞれ1と2に設定されている.
その後、絵を描きながら問題を解き、問題がフィボナッチ数列であることを発見し、for文でbottom-upでフィボナッチ関数を実現しました.
次は上から下へと問題を解きます.

package DynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1463 {
    public static int dp[];
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        dp=new int[N+1]; //초기값 0
        System.out.println(Dynamic(N));

    }
    public static int Dynamic(int N){
        if(N==1) return 0;
        if(dp[N]>0) return dp[N];
        dp[N] = Dynamic(N-1)+1;
        if(N%3==0) dp[N] = Math.min(dp[N],Dynamic(N/3) +1);
        if(N%2==0) dp[N] = Math.min(dp[N],Dynamic(N/2) +1);
        return dp[N];

    }

}