연말 상여금 - 동적 기획 법

샤 오 둥 이 있 는 회 사 는 연말 상여금 을 주 려 고 하 는데 샤 오 둥 은 마침 최고 복 지 를 받 았 다. 그 는 회사 연례 회의 에서 추첨 게임 에 참여 하려 고 한다. 게임 은 6 * 6 의 바둑판 에서 진행 되 고 그 위 에 36 개의 가치 가 다른 선물 이 놓 여 있다. 작은 바둑판 위 에 선물 이 하나 놓 여 있다. 그 는 왼쪽 상단 에서 게임 을 시작 해 야 한다. 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있다.오른쪽 아래 에 도착 하면 멈 추고 가 는 길에 있 는 격자 안의 선물 을 작은 동쪽 에서 도 받 을 수 있 습 니 다. 작은 동쪽 이 가장 가치 있 는 선물 을 받 을 수 있 도록 알고리즘 을 설계 하 세 요.
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];
    }
}