题目链接

思路

1. 思路同剑指42题总结的那样，当前元素节点的值取决于之前的情况选择。这道题可以根据动归思路来做
2. 首先考虑当前节点的最大价值如何决定。根据分析，当前节点的元素最大值取决于两种情况。设当前元素在i,j位置, 即 grid[i][j],价值矩阵为valueMatrix[][],这里保存每个格子的最大价值

• 因为情况规定拿礼物的时候是只能向右拿或者向下拿，所以相对的，上一步对于当前这一步来讲，就是左边或者上边的格子
• 考虑当前格子的最大值即 当前 格子价值+Max(左边相邻格子,上边相邻格子)，即可推导公式 valueMatrix[i][j] = grid[i][j] + Max(valueMatrix[i-1][j], valueMatrix[i][j-1])

3. 得到当前价值公式后，考虑到边界条件，可以先初始化第一行和第一列元素
   valueMatrix[0][j] = grid[0][j] + valueMatrix[0][j-1]
   valueMatrix[i][0] = grid[i][0] + valueMatrix[i-1][0]

class Solution {
    public int maxValue(int[][] grid) {
        // 动态规划，更新格子最大值
        // 这里每个格子的最大值是根据两个方向决定的，上方的格子的最大值或者右边格子的最大
        // 即 状态转移公式为 valueMatrix[i][j] = Math.max(valueMatrix[i-1][j],valueMatrix[i],[i-1]) +  grid[i][j];
        // 可以先初始化第一行和第一列，然后再从第二行第二列开始依次遍历
        if (grid.length == 0) return 0;

        int rowMax = grid.length; // 最大行数
        int colMax = grid[0].length; // 最大列数
        // 构建价值矩阵，表示每个位置的最大价值
        int[][] valueMatrix = new int[rowMax][colMax];
        valueMatrix[0][0] = grid[0][0];
        // 初始化第一行和第一列
        for (int k = 1; k < colMax; k++) {
            valueMatrix[0][k] = valueMatrix[0][k-1]+grid[0][k];
        }

        for (int k = 1; k < rowMax;k++) {
            valueMatrix[k][0] = valueMatrix[k-1][0] + grid[k][0];
        }
        // 每行遍历更新
        for(int j = 1; j < rowMax; j++) {
	    // 每列遍历更新
            for (int k = 1; k < colMax; k++) {
                valueMatrix[j][k] = Math.max(valueMatrix[j-1][k],valueMatrix[j][k-1]) + grid[j][k];
            }
        } 
        return valueMatrix[rowMax - 1][colMax - 1];
    }
}

Q.E.D.