提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

礼物的最大价值（剑指offer 47）

2023-03-14 22:52:12 时间

一、题目描述


        在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达


示例 1:

输入: 

[

  [1,3,1],

  [1,5,1],

  [4,2,1]

]

输出: 12

解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物


提示：

0 < grid.length <= 200

0 < grid[0].length <= 200


二、思路讲解 


对于我这种算法小白来说，一步一步往下走的题一律视作动态规划。那么动态规划就需要找到递推式。


我们不难发现，右下角的最大价值其实是max{上面一格的最大值，左边一格的最大值} ，因此，我们建立数组dp，dp[i][j]表示到达(i,j)时的最大价值。


下面就是考虑边界问题，在最左边的时候，价值只跟上面一格有关；在最上面的时候，价值只跟左边一格有关；左上角的顶点最大价值就是他本身。


三、Java代码实现


class Solution {
    public int maxValue(int[][] grid) {
 
        //dp[i][j]表示到达(i,j)时的最大数
        int [][]dp = new int [grid.length][grid[0].length];
        
        dp[0][0] = grid[0][0];
        for(int i=0; i<grid.length; i++) {
            for(int j=0; j<grid[0].length; j++) {
                
                
                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 if(i!=0 && j!=0) {
                    dp[i][j] = dp[i][j-1]>dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
                    dp[i][j] = dp[i][j]  + grid[i][j];
                }
                
            }
        }
        
        return dp[grid.length-1][grid[0].length-1];
    }
}


四、时空复杂度分析 


时间复杂度：        平方阶        要将二维数组遍历一遍

空间复杂度：        平方阶        使用一个二维数组


五、代码优化 


1、优化空间

        

因为在dp数组中我们只使用每一格的上面一格和左边一格，grid数组只使用当前一格 ，所以我们可以无需申请dp数组，直接将grid数组覆盖即可

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) 
                    continue;
                if(i == 0) 
                    grid[i][j] += grid[i][j - 1] ;
                else if(j == 0) 
                    grid[i][j] += grid[i - 1][j];
                else 
                    grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
}


空间复杂度可以降为常量阶


2、比较次数优化 

       

由于二维数组中处于边界的格子是少数，而在我们的算法中每一个格子都要判断是否处于两条边界上，显然浪费了时间。


我们可以先把第一行和第一列初始化出来，这样就可以省去判断的时间。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) 
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
 
        return grid[m - 1][n - 1];
    }
}



相关文章