题解 | #礼物的最大价值#

礼物的最大价值

http://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134

题目的主要信息：

一个 $m * n$ 的棋盘中每个格子都有一个礼物，价值各自记录在矩阵中
需要从棋盘左上角走到右下角，经过某个格子，该格子记录的价值就累加
每次只能往下或者往右，求能够获得的最大价值

举一反三：

学习完本题的思路你可以解决如下题目：

方法一：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

如果我们现在已经身处最右下角的一个格子，获取了这个礼物，那我们肯定是加上来自左边累计的最大礼物价值与来自上边累计的最大礼物价值的较大值，这样我们能获取的礼物价值才会更大，因此我们用 $d p [i] [j]$ 表示从左上角到第i行第j列的格子总共能获取的最大价值，因此转移方程为 $d p [i] [j] = g r i d [i] [j] + m a x (d p [i - 1] [j], d p [i] [j - 1])$ .

同时因为在遍历的时候我们可以将累加的礼物价值的dp数组直接添加在原数组grid中，这样我们可以省下一个辅助空间。

具体做法：

step 1：初始化第一列，每个元素只能累加自上方。
step 2：初始化第一行，每个元素只能累加自左方。
step 3：然后遍历数组，对于每个元素添加来自上方或者左方的较大值。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public int maxValue (int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //第一列只能来自上方
        for(int i = 1; i < m; i++)
            grid[i][0] += grid[i - 1][0];
        //第一行只能来自左边
        for(int i = 1; i < n; i++)
            grid[0][i] += grid[0][i - 1];
        //遍历后续每一个位置
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                //增加来自左边的与上边的之间的较大值
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
        return grid[m - 1][n - 1];
    }
}

C++实现代码：

class Solution {
public:
    int maxValue(vector<vector<int> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        //第一列只能来自上方
        for(int i = 1; i < m; i++)
            grid[i][0] += grid[i - 1][0];
        //第一行只能来自左边
        for(int i = 1; i < n; i++)
            grid[0][i] += grid[0][i - 1];
        //遍历后续每一个位置
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                //增加来自左边的与上边的之间的较大值
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);
        return grid[m - 1][n - 1];
    }
};

Python实现代码：

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        #第一列只能来自上方
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        #第一行只能来自左边
        for i in range(1, n):
            grid[0][i] += grid[0][i - 1]
        #遍历后续每一个位置
        for i in range(1, m):
            for j in range(1, n):
                #增加来自左边的与上边的之间的较大值
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1])
        return grid[m - 1][n - 1]

复杂度分析：

时间复杂度： $O (m n)$ ，其中 $m$ 、 $n$ 分别为矩阵的边长，遍历整个矩阵
空间复杂度： $O (1)$ ，原数组中修改，无额外辅助空间

方法二：记忆化递归（扩展思路）

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。