검지Offer 47번--선물의 최대 가치

1148 단어
한 mxn의 바둑판의 한 칸마다 선물이 놓여 있다. 모든 선물은 일정한 가치(0보다 크다)가 있다. 바둑판의 왼쪽 상단에서 시작하여 매번 오른쪽이나 아래로 한 칸을 이동할 수 있고 바둑판의 오른쪽 하단에 도달하는 것을 알 수 있다.바둑판과 위의 선물을 주어 우리가 최대 얼마의 가치를 받을 수 있는지 계산하다
전형적인 동태적 기획 문제, 동태적 기획은 중첩자 문제와 최우수자 구조 성격의 문제에 종종 적용된다.도착지에는 두 가지 상황이 있다.
  • 왼쪽에서 바로
  • 위에서 오면
  • 종점까지 가서 얻을 수 있는 가치의 최대치, 즉 각 하위 문제의 최대치, 즉 각 칸에 도달하기 위해 받은 선물의 가치가 모두 가장 크다. 즉, 취하면 현재 칸이 가장 큰 선물 가치를 얻을 수 있다는 것을 알 수 있다. 현재 칸의 왼쪽 칸과 위에 있는 칸의 최대 선물 가치와
    public int getMaxVal(int[] gifts, int rows, int cols) {
            if (gifts == null || gifts.length == 0)
                return 0;
            int[][] maxVal = new int[rows][cols];
            for (int row = 0; row < rows; row++) {
                for (int col = 0; col < cols; col++) {
                    int left = 0;
                    int up = 0;
                    if (row > 0) {
                        up = maxVal[row - 1][col];
                    }
                    if (col > 0) {
                        left = maxVal[row][col - 1];
                    }
                    maxVal[row][col] = Math.max(up, left) + gifts[row * col + col];
                }
            }
            return maxVal[rows - 1][cols - 1];
        }
    

    좋은 웹페이지 즐겨찾기