DPによる最安値の検索

DPでJavaで白俊2579号を解読しました.
原理は前の9095号とほぼ同じと言える.

条件に従って移動

1マスか2マスしか移動できない条件で、点火式を作ればいいです.また、最も値を求める必要があるので、可能な経路の中でどの値が大きいかを判別するだけでよい.

最後に1つだけ移動するとします。

前のマスは上のマスだけで、前のマスと到着マスの2マスをカバーしており、その前に到着点の前の3マスから出発しなければならない.の言葉で説明すると少しめまいがしますが、画像で見るともっと直感的です.
6号車を到着点とする.5号車から1両移動して到着すると、5、6はすでに2両連続しており、その前に3号車から移動しなければならない.次のように記述します.(各セルの最大値はmax[]であり、各セルのスコアはscore[]である)max[6] = max[3] + score[5] + score[6]

最後に2コマ移動した場合

最後のmoveが2コマ移動する場合は、2コマ前の最低価格に到達点の点数を加えればよい.画像と方式で確認してみます.
4号車の最低価格に6号車の点数を加えればいいです.max[6] = max[4] + score[6]

最低価格を求める

では、上記の2つのケースを導出した場合、その中の最値を実際のmax[n]値として保存すればよい.私はまず1、2、3号車を直接初期化し、4号車からforドアでBoottom-up方式でmax列を初期化しました.

max[6] = max[3] + score[5] + score[6]

max[6] = max[4] + score[6]=> max[6] = Math.max(1번, 2번)

次は私が提出したコードです.

import java.util.*;
import java.io.*;

public class boj2579 {
    static int n,score[] = new int[301], max[] = new int[301];

    static void DP(){
        max[1] = score[1];
        max[2] = score[1] + score[2];
        max[3] = Math.max(score[1]+score[3], score[2]+score[3]);

        for(int i=4; i<n+1; i++)
            max[i] = Math.max(max[i-2] + score[i], max[i-3] + score[i-1] + score[i]);
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());

        for(int i=1; i<=n; i++){
            stk = new StringTokenizer(bfr.readLine());
            score[i] = Integer.parseInt(stk.nextToken());
        }
        DP();
        System.out.println(max[n]);
    }
}

最初にscore[]とmax[]をn+1のsizeに初期化した結果、ArrayIndexOutOfBoundsが表示されたので、与えられた入力値の範囲300に初期化され、良好な結果となった.