题目描述
在一个 $m\times n$ 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 $0$ )。
你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?
算法
一道 dp 水题,与数字三角形类似,那么按照 dp 的标准思路,我们分三步:
设 $f_{i,j}$ 表示从 $(0,0)$ 走到 $(i,j)$ 能拿到的最大价值。
因为在每个位置,我们可以从其上方及其左方走来,理所当然,我们也从左方与上方转移状态。
$$ f_{i,j}=\max\{f_{i-1,j},f_{i,j-1}\}+a_{i,j} $$
虽然这道题这样就能 $\texttt{AC}$ ,但我们仍要尝试对其进行优化:
由于我们要对每一个状态进行状态转移,而状态又无法优化,所以我们想从时间上优化的思路失败了。
输入数据已经给了一个数组,我们是否要再开一个数组呢?
我们可以发现,在每次转移中,$a_{i,j}$ 总共只用了一次,也就是说在更新 $f_{i,j}$ 后 $a_{i,j}$ 就没用了。
所以我们可以直接用 $a$ 数组作为我们储存 dp 状态的数组,那么我们就不用去在开一个 $f$ 数组了。
代码
class Solution {
public:
int getMaxValue(vector<vector<int>>& a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i && j) a[i][j] += max(a[i - 1][j], a[i][j - 1]);
else if (i) a[i][j] += a[i - 1][j];
else if (j) a[i][j] += a[i][j - 1];
}
}
return a.back().back();
}
};
class Solution(object):
def getMaxValue(self, a):
n, m = len(a), len(a[0])
for i in range(n):
for j in range(m):
if i > 0 and j > 0: a[i][j] += max(a[i - 1][j], a[i][j - 1])
elif i > 0: a[i][j] += a[i - 1][j]
elif j > 0: a[i][j] += a[i][j - 1]
return a[-1][-1]
膜拜大佬
太强了
太强了
牛
茅塞顿开,真香的代码!!膜拜大佬!
666
牛逼牛逼,五体投地
大佬 大佬 膜拜大佬
%%%