剑指offer-72、礼物的最⼤价值
<h2 id="题描述">题⽬描述</h2><p>在⼀个m × n的棋盘的每⼀格都放有⼀个礼物，每个礼物都有⼀定的价值（价值⼤于 0）。你可以从棋盘的左上⻆开始拿格⼦⾥的礼物，并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯的礼物的价值，请计算你最多能拿到多少价值的礼物？</p>
<p>如输⼊这样的⼀个⼆维数组，</p>
<pre><code class="language-txet">[
,
,
]
</code></pre>
<p>那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为 12</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="基础动态规划">基础动态规划</h3>
<p>这道题其实⼀看就知道是动态规划，棋盘中的每个⼩格⼦，都是和上⽅，或者左⽅的格⼦有关。既然是动态规划，那么我们先定义状态：</p>
<p><code>dp</code>表示到达(i,j)位置时能获得的最大礼物价值</p>
<p>状态转移：<code>dp = max(dp, dp) + grid</code></p>
<pre><code class="language-java">public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid.length;
int[][] dp = new int;
// 初始化起点
dp = grid;
// 初始化第一行：只能从左边来
for (int j = 1; j < n; j++) {
dp = dp + grid;
}
// 初始化第一列：只能从上边来
for (int i = 1; i < m; i++) {
dp = dp + grid;
}
// 填充其余位置
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp = Math.max(dp, dp) + grid;
}
}
return dp;
}
</code></pre>
<p>每个位置的计算只依赖左边和上边的结果，通过双重循环自左上向右下填充整个dp表</p>
<ul>
<li>时间复杂度：O(mn)</li>
<li>空间复杂度：O(mn)</li>
</ul>
<h3 id="空间优化动态规划">空间优化动态规划</h3>
<p>观察发现当前行只依赖上一行，可以使用一维数组进行空间优化，利用<code>dp</code>在更新前存储上一行第j列的值，更新后存储当前行第j列的值，实现空间复用</p>
<p><code>dp</code>表示当前行第j列的最大价值，滚动更新</p>
<pre><code class="language-java">public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid.length;
int[] dp = new int;
// 初始化第一行
dp = grid;
for (int j = 1; j < n; j++) {
dp = dp + grid;
}
// 处理后续行
for (int i = 1; i < m; i++) {
// 更新第一列
dp += grid;
for (int j = 1; j < n; j++) {
// dp代表上一行第j列的值（从上方来）
// dp代表当前行第j-1列的值（从左边来）
dp = Math.max(dp, dp) + grid;
}
}
return dp;
}
</code></pre>
<ul>
<li>时间复杂度：O(mn)</li>
<li>空间复杂度：O(n)</li>
</ul>
<h3 id="原地修改动态规划最优解">原地修改动态规划（最优解）</h3>
<p>修改原数组，直接使用grid数组作为dp表，避免额外空间分配</p>
<pre><code class="language-java">public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid.length;
// 初始化第一行
for (int j = 1; j < n; j++) {
grid += grid;
}
// 初始化第一列
for (int i = 1; i < m; i++) {
grid += grid;
}
// 填充其余位置
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid += Math.max(grid, grid);
}
}
return grid;
}
</code></pre>
<ul>
<li>时间复杂度： O(nm) ，需要计算完⾥⾯的⼩格⼦</li>
<li>空间复杂度： O(1) ，优化后可以实现原地操作，不需要额外的空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19558972
頁:
[1]