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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
 */
function maxValue( grid ) {
    // write code here
    const cache = new Array(grid.length)
    for (let i = 0; i < grid.length; i++) {
        cache[i] = new Array(grid[0].length)
    }
    cache[0][0] = grid[0][0]

    for (let i = 1; i < grid.length; i++) {
        cache[i][0] = cache[i - 1][0] + grid[i][0]
    }
    for (let i = 1; i < grid[0].length; i++) {
        cache[0][i] = cache[0][i - 1] + grid[0][i]
    }
    for (let i = 1; i < grid.length; i++) {
        for (let j = 1; j < grid[0].length; j++) {
            cache[i][j] = grid[i][j] + Math.max(cache[i - 1][j], cache[i][j - 1])
        }
    }
    return cache[grid.length - 1][grid[0].length - 1]
}

module.exports = {
    maxValue : maxValue
};