题目
LeetCode-链接直达
给定一个二维数组, 每一步只能向下或向右移动, 求在从二维数组的\([0][0]\)位移动到\([m-1][n-1]\)的过程中,
经过位置的值之和的最大值.
自己的想法
自己的想法 X 看了别人的想法之后自己的理解 √
一个递推方程, 如果要保证走到最后的值最大, 则需要每一步都是最大的.
\begin{equation} dp(i, j) = \begin{cases} grid(i, j), & i = 0, j
= 0 \\ grid(i, j) + dp(i, j - 1), & i = 0, j \neq 0 \\ grid(i, j) +
dp(i - 1, j), & i \neq 0, j = 0 \\ grid(i, j) + \max(dp(i - 1, j),
dp(i, j - 1)), & i \neq 0,j \neq 0 \end{cases} \end{equation}
其实就是递归地把整个二维数组中从开始到每个位置的路过值之和的最大值求出来,
是贪心还是动态规划啊.
自己再遇到这种问题的时候可以想一下有没有什么递推公式可以用来解决这个问题,
数学归纳法.
题解
根据上面的方程, 写出对应的代码还是不难的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) dp[i][j] = grid[i][j];
else if (i == 0 && j != 0) dp[i][j] = dp[i][j - 1] + grid[i][j];
else if (i != 0 && j == 0) dp[i][j] = dp[i - 1][j] + grid[i][j];
else dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
};
|
时间复杂度为\(O(mn)\),
空间复杂度为\(O(mn)\).
由于整个遍历过程是从上往下从左至右一行一行遍历的,
其实也可以在原数组上进行计算, 这样空间复杂度就只有\(O(1)\)了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) grid[i][j] = grid[i][j];
else if (i == 0 && j != 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
else if (i != 0 && j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
else grid[i][j] = grid[i][j] + max(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}
};
|
