연말 상여금 - 동적 기획 법
1170 단어 각 대기업 프로 그래 밍 문제
6 * 6 의 행렬 board 를 지정 합 니 다. 그 중에서 모든 요 소 는 해당 칸 의 선물 가치 이 고 왼쪽 상단 은 [0, 0] 입 니 다. 얻 을 수 있 는 최대 가 치 를 되 돌려 주 십시오. 모든 선물 가치 가 100 보다 많 고 1000 보다 적 음 을 보장 합 니 다.
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int n = board.length;
int[][] dp = new int[n][n];
dp[0][0] = board[0][0];
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i-1]+board[0][i];
dp[i][0] =dp[i-1][0]+board[i][0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];
}
}
return dp[n - 1][n - 1];
}
}