分享题解09:礼物的最大价值
2021/9/10 23:05:06
本文主要是介绍分享题解09:礼物的最大价值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:礼物的最大价值
描述
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
// 输入: [ [1,3,1], [1,5,1], [4,2,1] ] // 输出: 12 // 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
第一种解题思路
每次只能向下或向右
第一行:自己 = 自己 + 前面
第一列:自己 = 自己 + 上面
其余位置:自己 = 自己 + max{上面位置,前面位置}
返回终点位置的数值即为所求
var maxValue = function (grid) { var m = grid.length, n = grid[0].length; for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { if (i == 0 && j == 0) { continue; } if (i == 0) { grid[i][j] += grid[i][j - 1]; } else if (j == 0) { grid[i][j] += grid[i - 1][j]; } else { grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); } } } return grid[m - 1][n - 1]; };
第二种解题思路 DFS
知道DFS 的人应该最容易想到的办法就是这种了。
function maxFood(grid) { var m = grid.length; var n = grid[0].length; var endx = m; var endy = n; var vis = []; // vis 初始化 0 未访问 1 已访问 for (let i = 0; i < endx; i++) { vis[i] = []; for (let j = 0; j < endy; j++) { vis[i][j] = 0 } } var res = []; vis[0][0] = 1; // console.log(grid[0][0]); var resR = dfs(0, 0, grid[0][0]); console.log(resR) function dfs(x, y, sum) { if (x === endx - 1 && y === endy - 1) { // console.log('11'); res.push(sum); // console.log(sum); } else { // 下 if (x >= 0 && x + 1 < m && y >= 0 && y < n ) { // console.log('11') if (vis[x + 1][y] == 0) { vis[x + 1][y] = 1; dfs(x + 1, y, sum + grid[x + 1][y]); vis[x + 1][y] = 0 } } // 右 if (x >= 0 && x < m && y >= 0 && y + 1 < n ) { // console.log('22') if (vis[x][y + 1] == 0) { vis[x][y + 1] = 1; dfs(x, y + 1, sum + grid[x][y + 1]); vis[x][y + 1] = 0 } } } return Math.max.apply(null,res); } }
大家若有其他思路,期待大家私聊或留言探讨
不足之处望大家谅解
这篇关于分享题解09:礼物的最大价值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南