力扣 - 剑指 Offer 47. 礼物的最大价值
2024-08-31 23:20:49
题目
思路1
- 因为是要求最大价值,而且只能移动下方或者右方,因此,每个位置的最大值就是
本身的值
加上上边 / 左边 中的最大值
,然后每次遍历都可以复用上一次的值。因此我们可以得到状态转移方程:- $ dp[i][j]=\begin{matrix} max(dp[i-1][j], dp[i][j-1]) + grid[i][j] \end{matrix} $
- 我们可以创建一个行和列都要多一行的 dp 数组,这样子可以不用判断条件了,但是同时也要注意
grid
中的坐标都要减去 1,因为我们是从 1 开始的:
代码
class Solution {
public int maxValue(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
// 创建dp数组,让 row 和 col 都多创建一行就可以避免判断边界值问题
int dp[][] = new int[row+1][col+1];
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
// 这里的 grid 中 i-1 和 j-1 是因为我们是从 1 开始的,所以要减去 1 才是原始正确的位置
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
}
}
// 最后直接返回数组右下角值即可
return dp[row][col];
}
}
复杂度分析
- 时间复杂度:\(O(MN)\),
- 空间复杂度:\(O(MN)\),创建 dp 数组所花费的空间
思路2
- 然后我们可以优化一下,因为只能左走或者右走,因此第一行和第一列是固定的一条路,我们可以事先初始化计算一下第一行和第一列,到时就不用计算了。因此直接在原数组上直接进行就可以了
代码
class Solution {
public int maxValue(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
// 先初始化边界
for (int i = 1; i < row; i++) {
grid[i][0] += grid[i-1][0];
}
for (int i = 1; i < col; i++) {
grid[0][i] += grid[0][i-1];
}
// 遍历
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
// 选择左边或者上边
grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
}
}
// 最后直接返回数组右下角值即可
return grid[row-1][col-1];
}
}
复杂度分析
- 时间复杂度:\(O(MN)\),
- 空间复杂度:\(O(1)\),无需创建 dp 数组
最新文章
- JavaWeb监听器详解
- UIProgressView和UISlider
- ESXi5 中克隆Linux虚拟主机的网络配置
- Linux中内存查看命令free详解(转)
- apache多站点配置+多端口配置
- ASP.NET中生成rss.xml
- sparksql中行转列
- spring-boot+mybatis开发实战:如何在spring-boot中使用myabtis持久层框架
- MAC下secretCRT使用技巧(转)
- 记一次oracle crs无法重启事故
- 【Linux】Mac PD set centos static ip
- sha-hmac
- jq 字符串去除空格
- 【vue】vue +element 搭建项目,加(解)密
- LNMP 如何安装mongodb
- 在visual studio中设置点击左边选项卡中的类文件,右侧解决方案跳到对应的文件
- Scala进阶之路-正则表达式案例
- Version Control System
- Spark部署
- PCB常见的拓扑结构 (转)
热门文章
- BPMN 學習實例
- UltraSoft - Beta - Scrum Meeting 10
- 第1次 Beta Scrum Meeting
- 2020BUAA软工热身作业
- 你真的了解电子邮件系统的组成和结构吗?(SMTP、POP3、IMAP、MIME……)
- 洛谷 	 P5664 [CSP-S2019] Emiya 家今天的饭
- P2120 [ZJOI2007]仓库建设
- 关于dns服务工作的原理,和配置的细节理解。
- ORA-01756: quoted string not properly terminated
- 第三周PTA笔记 回文数+A-B(大数减法)+高精度除法+数楼梯(大数加法)