[プログラマー]縄張り取り(JAVA/Java)

質問リンク

に答える

DPで説明すればいい
横長が4に固定されているため,dpテーブルを4つに分けて充填した.
問題例を下図に示します.

まず、最初の行は元の地価に初期化される.

の2行目から見ると、한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없다というルールがあるので、1枚目の図のように、同じ列以外の他の列の値の最大値と元の値を加算することができます!すべての熱に対してこれをすればいいのです

まで下に進むと、右側と同じdpテーブルを埋め、最後の行で最大の値を選択すると結果値が得られます.

コード#コード#

class Solution {
    static int solution(int[][] land) {

        int n = land.length;

        int[][] dp = new int[n][4];
        for (int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][0];
            dp[i][1] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][1];
            dp[i][2] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3])) + land[i][2];
            dp[i][3] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2])) + land[i][3];
        }

        int answer = Math.max(Math.max(dp[n-1][0], dp[n-1][1]), Math.max(dp[n-1][2], dp[n-1][3]));


        return answer;
    }
}

整理する

난이도 : LEVEL 2

🤦‍♀️ メモ

今やっと点dpを使うことができて、,!一度で効率性が通ったので、気持ちの良い質問です.DPはこのように使うことができることを覚えています!!

コメントサイト

いいえ