[プログラマー]縄張り取り(JAVA/Java)
13127 ワード
質問リンク
DPで説明すればいい
横長が4に固定されているため,dpテーブルを4つに分けて充填した.
問題例を下図に示します.
まず、最初の行は元の地価に初期化される. の2行目から見ると、 まで下に進むと、右側と同じdpテーブルを埋め、最後の行で最大の値を選択すると結果値が得られます.
今やっと点dpを使うことができて、,!一度で効率性が通ったので、気持ちの良い質問です.DPはこのように使うことができることを覚えています!!
いいえ
に答える
DPで説明すればいい
横長が4に固定されているため,dpテーブルを4つに分けて充填した.
問題例を下図に示します.
한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없다
というルールがあるので、1枚目の図のように、同じ列以外の他の列の値の最大値と元の値を加算することができます!すべての熱に対してこれをすればいいのですコード#コード#
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
🤦♀️ メモ
コメントサイト
いいえ
Reference
この問題について([プログラマー]縄張り取り(JAVA/Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@yanghl98/프로그래머스-땅따먹기-JAVA자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol