题解 | #礼物的最大价值#

动态规划：状态标识f[i][j]表示从(0,0)走到(i,j)所能拿到礼物的最大价值。状态转移：只能从上方或者左方走到(i,j)，从上方走到(i,j)，那么拿到礼物的价值为f[i-1][j]+grid[i][j]；从左方走到(i,j)，那么拿到礼物的价值为f[i][j-1]+grid[i][j]。需要注意边界判断。两者取max即可。我这里对空间复杂度进行优化，只需要记录grid[i][j]的值即可优化空间复杂度。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        // write code here
        int n = grid.length, m = grid[0].length;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                int x = grid[i][j];
                if(i - 1 >= 0) {
                    grid[i][j] = Math.max(grid[i][j],x + grid[i-1][j]);
                }
                if(j - 1 >= 0) {
                    grid[i][j] = Math.max(grid[i][j],x + grid[i][j-1]);
                }
            }
        }
        return grid[n-1][m-1];
    }
}