剑指offer-礼物的最大价值-JavaScript
题目形容:在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有肯定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
解法:动态规划
公告状态数组dp是一个 m*n 的二维数组。dp[i][j]的默认值是 0,它的含义是:在坐标点(i,j)处,能得到的最大价值礼物。所以,整个棋盘的最大价值礼物就是 dp[m-1][n-1] 的值。
现在来看状态转移的过程:
- 出发点是左上角,且只能向右/下移动,所以第一列和第一行中的 dp 值,就等于:当前礼物价值+上一个 dp 值
- 对于一般坐标(i,j),
dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/// 原文地址:https://xxoo521.com/2020-03-11-max-value-of-gift//** * @param {number[][]} grid * @return {number} */var maxValue = function(grid) { const rowNum = grid.length; const colNum = grid[0].length; const dp = []; for (let i = 0; i < rowNum; ++i) { dp[i] = []; for (let j = 0; j < colNum; ++j) { dp[i][j] = 0; } } 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 < colNum; ++j) { dp[0][j] = grid[0][j] + dp[0][j - 1]; } for (let i = 1; i < rowNum; ++i) { for (let j = 1; j < colNum; ++j) { dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[rowNum - 1][colNum - 1];};时间复杂度和空间复杂度都是。在 leetcode 上显示,内存击败 100%,时间击败 96.63%:
image
更多资料
整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我升级的动力 ??
- ??Blog:剑指 Offer 题解 + JS 代码
- ??Github : dongyuanxin/blog
- ?? 公众号:心谭博客
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 剑指offer-礼物的最大价值-JavaScript
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 剑指offer-礼物的最大价值-JavaScript