题目的主要信息:
  • 一个mnm*n的棋盘中每个格子都有一个礼物,价值各自记录在矩阵中
  • 需要从棋盘左上角走到右下角,经过某个格子,该格子记录的价值就累加
  • 每次只能往下或者往右,求能够获得的最大价值
举一反三:

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

JZ70. 矩形覆盖

JZ63. 买卖股票的最好时机(一)

JZ46. 把数字翻译成字符串

JZ71. 跳台阶扩展问题

方法一:动态规划(推荐使用)

知识点:动态规划

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

思路:

如果我们现在已经身处最右下角的一个格子,获取了这个礼物,那我们肯定是加上来自左边累计的最大礼物价值与来自上边累计的最大礼物价值的较大值,这样我们能获取的礼物价值才会更大,因此我们用dp[i][j]dp[i][j]表示从左上角到第i行第j列的格子总共能获取的最大价值,因此转移方程为dp[i][j]=grid[i][j]+max(dp[i1][j],dp[i][j1])dp[i][j] = grid[i][j]+max(dp[i-1][j],dp[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(mn)O(mn),其中mmnn分别为矩阵的边长,遍历整个矩阵
  • 空间复杂度:O(1)O(1),原数组中修改,无额外辅助空间
方法二:记忆化递归(扩展思路)

知识点:递归

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

思路:

同样考虑我们在最右下角这个位置,它可以选择来自左边的格子过来,也可以选择来自上边的格子过来,这样我们的问题可以从(m,n)(m,n)分解成(m1,n)(m-1,n)(m,n1)(m,n-1)这两个子问题,取子问题的最大值加上右下角这个礼物价值,因此可以用递归:

  • 终止条件: 到达右上角起点的时候,终止递归,即m与n都等于0.
  • 返回值: 将子问题的较大值加上本格子的礼物价值返回。
  • 本级任务: 判断是否是矩阵遍历,进入子问题计算。

具体做法:

  • step 1:使用一个二维辅助数组dp记录递归过程中的中间值。
  • step 2:递归时先判断是否到起点与是否到边界,边界只有一条递归路线。
  • step 3:如果dp数组中中有记录的值,直接返回,否则进入子问题求解后加到数组中。

Java实现代码:

import java.util.*;
public class Solution {
    private int recursion(int[][] grid, int m, int n, int[][] dp){
        //到达起点
        if(m == 0 && n == 0){
            dp[0][0] = grid[0][0];
            return grid[0][0];
        }
        //两个边界
        if(m == 0)
            dp[0][n] = grid[0][n] + recursion(grid, m, n - 1, dp);
        if(n == 0)
            dp[m][0] = grid[m][0] + recursion(grid, m - 1, n, dp);
        //如果有值可以直接返回
        if(dp[m][n] == 0)
            //递归求左边或者上边的最大值
            dp[m][n] = grid[m][n] + Math.max(recursion(grid, m - 1, n, dp), recursion(grid, m, n - 1, dp));
        return dp[m][n];
    }
    public int maxValue (int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //用于记忆递归过程中的值
        int[][] dp = new int[m][n];
        return recursion(grid, m - 1, n - 1, dp);
    }
}

C++实现代码:

class Solution {
public:
    int recursion(vector<vector<int> >& grid, int m, int n, vector<vector<int> >& dp){
        //到达起点
        if(m == 0 && n == 0){
            dp[0][0] = grid[0][0];
            return grid[0][0];
        }
        //两个边界
        if(m == 0)
            dp[0][n] = grid[0][n] + recursion(grid, m, n - 1, dp);
        if(n == 0)
            dp[m][0] = grid[m][0] + recursion(grid, m - 1, n, dp);
        //如果有值可以直接返回
        if(dp[m][n] == 0)
            //递归求左边或者上边的最大值
            dp[m][n] = grid[m][n] + max(recursion(grid, m - 1, n, dp), recursion(grid, m, n - 1, dp));
        return dp[m][n];
    }
    int maxValue(vector<vector<int> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        //用于记忆递归过程中的值
        vector<vector<int> > dp(m, vector<int>(n, 0));
        return recursion(grid, m - 1, n - 1, dp);
    }
};

Python实现代码:

class Solution:
    def recursion(self, grid: List[List[int]], m: int, n: int, dp: List[List[int]]) -> int:
        #到达起点
        if m == 0 and n == 0:
            dp[0][0] = grid[0][0]
            return grid[0][0]
        #两个边界
        if m == 0:
            dp[0][n] = grid[0][n] + self.recursion(grid, m, n - 1, dp)
        if n == 0:
            dp[m][0] = grid[m][0] + self.recursion(grid, m - 1, n, dp)
        #如果有值可以直接返回
        if dp[m][n] == 0:
            #递归求左边或者上边的最大值
            dp[m][n] = grid[m][n] + max(self.recursion(grid, m - 1, n, dp), self.recursion(grid, m, n - 1, dp))
        return dp[m][n]
    
    def maxValue(self , grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        #用于记忆递归过程中的值
        dp = [[0 for i in range(n)] for i in range(m)]
        return self.recursion(grid, m - 1, n - 1, dp)

复杂度分析:

  • 时间复杂度:O(mn)O(mn),其中mmnn分别为矩阵的边长,最坏递归需要填满dp数组
  • 空间复杂度:O(mn)O(mn),递归栈及记录中间值的辅助数组