연말 상여금

1901 단어
샤 오 둥 이 있 는 회 사 는 연말 상여금 을 주 려 고 하 는데 샤 오 둥 은 마침 최고 복 지 를 받 았 다. 그 는 회사 연례 회의 에서 추첨 게임 에 참여 하려 고 한다. 게임 은 6 * 6 의 바둑판 에서 진행 되 고 그 위 에 36 개의 가치 가 다른 선물 이 놓 여 있다. 작은 바둑판 위 에 선물 이 하나 놓 여 있다. 그 는 왼쪽 상단 에서 게임 을 시작 해 야 한다. 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있다.오른쪽 아래 에 도착 하면 멈 추고 가 는 길에 있 는 격자 안의 선물 을 작은 동쪽 에서 도 받 을 수 있 습 니 다. 작은 동쪽 이 가장 가치 있 는 선물 을 받 을 수 있 도록 알고리즘 을 설계 하 세 요.
6 * 6 의 행렬 board 를 지정 합 니 다. 그 중에서 모든 요 소 는 해당 칸 의 선물 가치 이 고 왼쪽 상단 은 [0, 0] 입 니 다. 얻 을 수 있 는 최대 가 치 를 되 돌려 주 십시오. 모든 선물 가치 가 100 보다 적 고 1000 보다 적 음 을 보증 합 니 다.
public class Main{

    //    
    //               =               +       
    public static int getMostValue(int[][] board) {
        int n = board.length;        //      n * n
        int[][] curMostValue = new int[n][n];    //             
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(i == 0 && j == 0) //               =       
                    curMostValue[i][j] = board[i][j];
                else if(i == 0) //           =          +       
                    curMostValue[i][j] = curMostValue[i][j - 1] + board[i][j];
                else if(j == 0) //           =          +       
                    curMostValue[i][j] = curMostValue[i - 1][j] + board[i][j];
                else //          = max(        ,         ) +       
                    curMostValue[i][j] = Math.max(curMostValue[i - 1][j], curMostValue[i][j - 1]) + board[i][j];
            }
        }
        return curMostValue[n - 1][n - 1]; //     curMostValue          
    }

    public static void main(String[] args) {
        int[][] board ={
                {2,2,1,1,2,1},
                {3,2,4,3,1,2},
                {1,2,5,4,1,3},
                {2,1,3,3,2,1},
                {1,3,2,4,1,2},
                {2,2,4,1,2,2}};
        System.out.println(getMostValue(board));
    }
}

좋은 웹페이지 즐겨찾기