[アルゴリズム]バックアップ-移動
伯俊-移動
ではdp[i][j]=Max(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+図[i][j]となる.インデックスがずれているかどうかを確認するだけです.
説明する
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class baekjoon_11048 {
static int N, M;
static int[][] graph, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
graph = new int[N][M];
dp = new int[N][M];
for (int i = 0; i < N; i++) {
inputs = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
graph[i][j] = Integer.parseInt(inputs[j]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i - 1 >= 0 && j - 1 >= 0) {
dp[i][j] = Math.max(dp[i - 1][j - 1] + graph[i][j], dp[i][j]);
}
if (i - 1 >= 0) {
dp[i][j] = Math.max(dp[i - 1][j] + graph[i][j], dp[i][j]);
}
if (j - 1 >= 0) {
dp[i][j] = Math.max(dp[i][j-1] + graph[i][j], dp[i][j]);
}
dp[i][j] = Math.max(dp[i][j], graph[i][j]);
}
}
System.out.println(dp[N-1][M-1]);
}
}
dp[i][j]は、位置[i][j]で持つことができる最大のキャンディ数である.ではdp[i][j]=Max(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+図[i][j]となる.インデックスがずれているかどうかを確認するだけです.
Reference
この問題について([アルゴリズム]バックアップ-移動), 我々は、より多くの情報をここで見つけました https://velog.io/@injoon2019/알고리즘-백준-이동하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol