剑指Offer——礼物的最大价值（JS实现）

var maxValue = function(grid) {
    // 首先构造一个和grid矩阵维度一致的矩阵
    const dp = [];
    const rowNum = grid.length;
    const cowNum = grid[0].length;
    for (let i = 0; i < rowNum;i++) {
        dp[i] = [];
        for (let j = 0;j < cowNum;j++) {
            dp[i][j] = 0;
        }
    }
    // 函数走到这里dp已经变成和grid维度完全一致的全零数组
    // 我们首先要做的是将dp的第一行和第一列全部填写为从初始位置出发走到目标位置所需的距离
    dp[0][0] = grid[0][0];
    for (let i = 1; i < rowNum;i++) {
        dp[i][0] = grid[i][0] + dp[i-1][0];
    }
    for (let j = 1; j < cowNum;j++) {
        dp[0][j] = grid[0][j] + dp[0][j-1]
    }
    // 通过上面两个循环我们已经将grid的第一行和第一列需要的价值和写到了dp数组中的第一列和第二列
    // 接下来遍历grid的其余数组即可
    for (let i = 1; i < rowNum;i++) {
        for (let j = 1;j < cowNum;j++) {
            dp[i][j] = grid[i][j] + Math.max(dp[i-1][j],dp[i][j-1]);
        }
    }
    // 走到这里dp数组的每一个值我们应该理解为grid数组路径的价值和
    // dp数组的最后一个值就应该是价值的最大值
    return dp[rowNum-1][cowNum-1]
};
```
作者：Always_positive
链接：https://juejin.cn/post/6948663870261035039
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。