剑指 Offer 47. 礼物的最大价值
题目链接
题目描述
在一个 m*n
的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0
)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示:
- 0 < g r i d . l e n g t h < = 200 0 < grid.length <= 200 0<grid.length<=200
- 0 < g r i d [ 0 ] . l e n g t h < = 200 0 < grid[0].length <= 200 0<grid[0].length<=200
分析:动态规划
我们定义
f
(
i
,
j
)
f(i,j)
f(i,j) 为从 (0,0)
到 (i-1,j-1)
所能获得的最大价值(定义 i
和 j
从 1
开始,避免边界问题)。
f ( i , j ) f(i,j) f(i,j) 只能由 上面 f ( i − 1 , j ) f(i-1,j) f(i−1,j) 和 左边 f ( i , j − 1 ) f(i,j-1) f(i,j−1) 转移而来。
因为是求得最大价值,我们就只能选择两者之间较大的那个,即
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
,
j
−
1
)
)
max( f(i-1,j) , f(i,j-1) )
max(f(i−1,j),f(i,j−1))。再加上当前 (i-1,j-1)
位置的价值 grid[i-1][j-1]
就是
f
(
i
,
j
)
f(i,j)
f(i,j)总的价值。
即, f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − 1 ) ) + g r i d [ i − 1 ] [ j − 1 ] f(i,j) = max( f(i-1,j) , f(i,j-1) ) + grid[i-1][j-1] f(i,j)=max(f(i−1,j),f(i,j−1))+grid[i−1][j−1]
时间复杂度: O ( n 2 ) O(n^2) O(n2)
C++代码:
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> f(m + 1,vector<int>(n+1));
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
f[i][j] = max(f[i-1][j],f[i][j-1]) + grid[i-1][j-1];
}
}
return f[m][n];
}
};
Java代码:
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] f = new int[m+1][n+1];
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
f[i][j] = Math.max(f[i-1][j],f[i][j-1]) + grid[i-1][j-1];
}
}
return f[m][n];
}
}
相关文章
- Java实现 LeetCode 764 最大加号标志(暴力递推)
- Java实现 LeetCode 215. 数组中的第K个最大元素
- java实现第九届蓝桥杯最大乘积
- Java实现最大连续乘积子数组
- (剑指Offer)面试题12:打印1到最大的n位数
- oracle修改最大连接数参数processes
- Leetcode.1561 你可以获得的最大硬币数目
- Leetcode.1139 最大的以 1 为边界的正方形
- 剑指 Offer II 005. 单词长度的最大乘积
- 虚拟机和Docker的最大区别
- 【[Offer收割]编程练习赛13 B】最大子矩阵(自己的思路)
- 华为OD机试 - 最大社交距离(Java & JS & Python)
- 华为OD机试 - 最大括号深度(Java & JS & Python)
- 面试题 16.07. 最大数值(C++)
- 剑指 Offer 42. 连续子数组的最大和
- Leetcode 2231. 按奇偶性交换后的最大数字(可以,一次过)
- 【LeetCode】1514.概率最大的路径
- 【53】最大子数组和【LeetCode】