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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
 */
function maxValue( grid ) {
    // 动态规划，dp[i][j]代表从左上角到第i行第j列的格子总共能获取的最大价值
    // 状态转移方程为 dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])
    // 也可以直接将累加的礼物价值直接添加在原数组grid中，省下一个辅助空间
    const dp = [];
    let m = grid.length;
    let n = grid[0].length;
    // 初始化二维数组dp
    for(let i = 0; i < m; i++){
        dp[i] = Array(n).fill(0);
    }
    dp[0][0] = grid[0][0];
    // 初始化第一列元素，其值为上方元素相加
    for(let i = 1; i < m; i++){
        dp[i][0] = grid[i][0] + dp[i - 1][0];
    }
    // 初始化第一行元素，其值为左边元素相加
    for(let i = 1; i < n; i++){
        dp[0][i] = grid[0][i] + dp[0][i - 1];
    }
    // 遍历后续每个位置
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m -1][n - 1];
}
module.exports = {
    maxValue : maxValue
};