礼物的最大价值
解题思路
-
状态定义： 设动态规划矩阵 dp ，dp(i,j) 代表从棋盘的左上角开始，到达单元格 (i,j) 时能拿到礼物的最大累计价值；
-
转移方程：
![]( "礼物的最大价值")
- 当 i = 0 且 j = 0 时，为起始元素；
- 当 i = 0 且 j != 0 时，为矩阵第一行元素，只可从左边到达；
- 当 i != 0 且 j = 0 时，为矩阵第一列元素，只可从上边到达；
- 当 i != 0 且 j != 0 时，可从左边或上边到达；
-
初始状态： dp[0][0] = grid[0][0]，即到达单元格 (0,0) 时能拿到礼物的最大累计价值为 grid[0][0]；
-
返回值： dp[m-1][n-1] ，m, n 分别为矩阵的行高和列宽，即返回 dp 矩阵右下角元素；
-
优化：
- 初始化第一列和第一行之后，可将前三个转移方程优化掉；
- 转移方程只需要：grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
图解
复杂度
-
时间复杂度： O(MN)， M、N 分别为矩阵行高、列宽，需遍历整个 grid 矩阵；
-
空间复杂度： O(1)，原地修改使用常数大小的额外空间；
代码实现
function maxValue(grid: number[][]): number {
let m = grid.length, n = grid[0].length;
// 初始化第一行
for (let i = 1; i < n; i++) {
grid[0][i] += grid[0][i - 1];
}
// 初始化第一列
for (let i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
}
// 两个for循环推导，对于(i,j)来说，只能由上方或者左方转移过来
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
// m、n 为矩阵的宽高，索引要减 1
return grid[m - 1][n - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
第 3️⃣ 座大山：DOM 事件案例
上一篇
评论
