動的計画法（DP）とは

複雑な問題を、より小さな部分問題に分割して解き、それらの部分解を使って元の問題を解決する手法

ポイント

dp[i]=1～iまでの最短を記録

基本

問題:ダンジョン

あるダンジョンにはN個の部屋があり、1からNまでの番号がつけられている。このダンジョンは一方通行であり通路を介して一つ先または二つ先の部屋に移動することができる。各通路における移動時間は以下

部屋i-1から部屋iに向かう通路を通るのにAi分(2<=i<=N)かかる
部屋i-2から部屋iに向かう通路を通るのにBi分(2<=i<=N)かかる

太郎君が部屋1から部屋Nに移動するのに最短何分かかるか求めるプログラムを作成せよ

alg.java

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        // 配列サイズをN+1にして1-Nのインデックスを使用
        int[] A = new int[N+1];
        int[] B = new int[N+1];
        
        for(int i=2; i<=N; i++){
            A[i] = sc.nextInt();
        }
        for(int i=3; i<=N; i++){
            B[i] = sc.nextInt();
        }
        
        // 動的計画法
        int[] dp = new int[N+1];
        dp[1] = 0;
        if(N >= 2) dp[2] = A[2];
        
        for(int i=3; i<=N; i++){
            dp[i] = Math.min(dp[i-1] + A[i], dp[i-2] + B[i]);
        }
        
        System.out.println(dp[N]);
        sc.close();
    }
}

i=3以降→部屋 i に来る方法は2通りしかない
- 部屋 i-1 から来る→時間：dp[i-1] + A[i]
- 部屋 i-2 から来る→時間：dp[i-2] + B[i]
この 2つのうち短い方を選ぶ

ex.java

dp[i] = Math.min(dp[i-1] + A[i], dp[i-2] + B[i]);

問題:足場（ダンジョンとほぼ一緒）

N個の足場があり、左からi番目の足場iの高さはhi。カエルは次の二種類の行動を繰り返すことで足場1から足場Nに移動したい

足場i-2から足場iにコスト|h(i-2)-hi|かけて移動する
足場i-1から足場iにコスト|h(i-1)-hi|かけて移動する

移動にかかる合計コストの最小値を出力するプログラムを作成せよ。計算量はO(N)が望ましい

alg.java

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] foothold = new int[N+1];
        for(int i=1; i<=N; i++){
            foothold[i] = sc.nextInt();
        }
        
        //dp[]で最少コストを管理
        int[] dp = new int[N+1];
        dp[1] = 0;
        if(N >= 2) dp[2] = Math.abs(foothold[1] - foothold[2]);
        
        for(int i=3; i<=N; i++){
            dp[i] = Math.min(
                dp[i-1] + Math.abs(foothold[i-1] - foothold[i]),
                dp[i-2] + Math.abs(foothold[i-2] - foothold[i])
            );
        }
        System.out.println(dp[N]);
        sc.close();
    }
}

動的計画法の復元

問題:ダンジョン最短移動方法を示す

前回の問題例では最短何分かかるかを計算したが、今度は最短時間で移動する「方法」を一つ出力するプログラムを作成せよ。あり得る答えが二通り以上ある場合、そのうち一つを出力すればよい

alg.java

import java.util.Scanner;
import java.util.ArrayList;//経路を動的に格納
import java.util.Collections;//リストの逆順用

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N+1]; //i→i+1にかかる移動時間
        int[] B = new int[N+1]; //i→i+2にかかる移動時間
        
        for(int i=2; i<=N; i++){
            A[i] = sc.nextInt();
        }
        for(int i=3; i<=N; i++){
            B[i] = sc.nextInt();
        }
        int[] dp = new int[N+1];  
        dp[1] = 0;
        if(N >= 2) dp[2] = A[2];
        //DPで最短経路を記録
        for(int i=3; i<=N; i++){
            dp[i] = Math.min(dp[i-1] + A[i], dp[i-2] + B[i]);  
        }
        // 答えの復元
        // 変数Placeは現在位置(ゴールから進んでいく)
        //Answerリストに部屋番号を記録
        ArrayList<Integer> Answer = new ArrayList<>();  
        int Place = N;
        while(true){
            Answer.add(Place);  
            if(Place == 1) break; //部屋1まで戻ったら終わり
            //どこから部屋Placeに向かうのが最適か求める
            if(Place >= 2 && dp[Place-1] + A[Place] == dp[Place]){
            //AでPlaceにたどり着いてた場合
                Place = Place - 1;
            } else {
                Place = Place - 2; //BでPlaceにたどり着いてた場合
            }
        }
        
        // 変数Answerは「ゴールからの経路」になっているので逆順にする
        Collections.reverse(Answer);
        
        // 経路を出力
        for(int i = 0; i < Answer.size(); i++){
            if(i > 0) System.out.print(" ");
            System.out.print(Answer.get(i));
        }
        System.out.println();
        
        sc.close();
    }
}

問題：足場最短移動方法を示す

前回の足場問題について、最小コストで移動する具体的な方法を出力せよ

alg.java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] foothold = new int[N+1];
        for(int i=1; i<=N; i++){
            foothold[i] = sc.nextInt();
        }
        
        //dp[]で最少コストを管理
        int[] dp = new int[N+1];
        dp[1] = 0;
        if(N >= 2) dp[2] = Math.abs(foothold[1] - foothold[2]);
        
        for(int i=3; i<=N; i++){
            dp[i] = Math.min(
                dp[i-1] + Math.abs(foothold[i-1] - foothold[i]),
                dp[i-2] + Math.abs(foothold[i-2] - foothold[i])
            );
        }
        
        // 答えの復元
        ArrayList<Integer> Answer = new ArrayList<Integer>();
        int Place = N;
        while(true){
            Answer.add(Place);
            if(Place == 1) break;
            
            // 1つ前から来たかチェック
            if(Place >= 2 && dp[Place] == dp[Place-1] + Math.abs(foothold[Place-1] - foothold[Place])){
                Place = Place - 1;
            } else {
                Place = Place - 2;
            }
        }
        
        // whileループの外で逆順処理
        Collections.reverse(Answer);
        
        // 出力
        for(int i = 0; i < Answer.size(); i++){
            if(i > 0) System.out.print(" "); //i = 0（最初の要素）の時：空白を出力しない
            System.out.print(Answer.get(i)); //get() の引数には、**取得したい要素のインデックス（位置）を指定
        }
        System.out.println();
        
        sc.close();
    }
}