題目

在一個(gè) m*n 的棋盤的每一格都放有一個(gè)禮物，每個(gè)禮物都有一定的價(jià)值（價(jià)值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動(dòng)一格、直到到達(dá)棋盤的右下角。給定一個(gè)棋盤及其上面的禮物的價(jià)值，請(qǐng)計(jì)算你最多能拿到多少價(jià)值的禮物？

示例 1:

輸入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
輸出: 12
解釋: 路徑 1→3→5→2→1 可以拿到最多價(jià)值的禮物

分析

標(biāo)準(zhǔn)的遞歸動(dòng)態(tài)規(guī)劃，這種題目前幾次做不懂比較正常，熟能生巧。

第一次

class Solution {
    public int maxValue(int[][] grid) {
        if (grid == null || grid[0].length == 0) return 0;
        return move(grid, 0, 0, new int[grid.length][grid[0].length]);
    }

    public int move(int[][] grid, int i, int j, int[][] mem) {
        int rightMax = 0, downMax = 0;

        if (mem[i][j] != 0) {
            return mem[i][j];
        }

        if (i + 1 < grid.length) {
            rightMax = move(grid, i + 1, j, mem);
        }

        if (j+1 < grid[0].length) {
            downMax = move(grid, i, j + 1, mem);
        }

        mem[i][j] = Math.max(rightMax, downMax) + grid[i][j];
        return mem[i][j];
    }
}