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

// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  * 
//  * @param grid int整型二维数组 
//  * @return int整型
//  */
// function maxValue( grid ) {
//     // write code here
//     let m=grid.length
//     let n=grid[0].length
//     let dp = []
//     for (let i = 0; i < m ;i++) {
//         dp[i] = []
//         for (let j = 0;j < n;j++) {
//             dp[i][j] = 0
//         }
//     }
//     let gift=0
//     dp[0][0]=grid[0][0]
//     for(let i=1;i<n;i++){
//         dp[0][i]+=grid[0][i]
//     }
//     for(let j=1;j<m;j++){
//         dp[j][0]+=grid[j][0]
//     }
//     for(let i=1;i<m;m++){
//         for(let j=1;j<n;n++){
//             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
// };

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
 */

function maxValue( grid ) {
    // write code here
    // 递归：对于某一个坐标的路线最大值，就是这个坐标值加他的上面或者左边坐标的最大值（取大）。
    // 首先构造一个和grid矩阵维度一致的矩阵
    let dp = [];
    let rowNum = grid.length;
    let 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每个位置已填了0，下面给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]
    }
    //递归其他的路径最大值,这里递归的终点就是i=0或者j=0，即上面已经给dp赋过的值
    for(let i = 1;i<rowNum;i++){
        for(let j=1;j<cowNum;j++){
            dp[i][j]= Math.max(grid[i][j]+dp[i-1][j],grid[i][j]+dp[i][j-1])
        }
    }
    return dp[rowNum-1][cowNum-1] //返回dp右下角的值即为最大路径值
}
    
module.exports = {
    maxValue : maxValue
};