本文共 1380 字，大约阅读时间需要 4 分钟。

题目链接：

题目描述： 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例1：

输入: [  [1,3,1],  [1,5,1],  [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

数据范围：

0 < grid.length <= 2000 < grid[0].length <= 200

常规动态规划题，和差不多。借用一张图描述状态方程。

记忆化做法： 直接递归搜索答案会正确，但是会超时，在dfs(n-1,m-1)对应的调用关系树中，dfs(3,2)被计算了两次（一次是dfs（3,1）需要的，一次是dfs（2,2）需要的）。也许读者会认为重复算一两个数没有太大影响，但事实是：这样的重复不是单个结点，而是一颗子树。如果棋盘有n层，则调用关系树也会有n层，一共有$2^n-1$个结点。因此我们采用dp数组保存中间计算结果，已经计算过了的就不再进行计算。 代码：

class Solution {
       private int dp[][]=new int[202][202];    public int maxValue(int[][] grid) {
           int row=grid.length;        int col=grid[0].length;        for(int i=0;i<=row;i++){
               for(int j=0;j<=col;j++){
                   dp[i][j]=-1;            }        }        /*动态规划，其实可以原地数组，也就是直接使用grid保存答案，当然也可以将dp压缩至一维，二维方便理解        int dp[][]=new int[row+1][col+1];        for(int i=1;i<=row;i++){            for(int j=1;j<=col;j++){                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];            }        }        return dp[row][col];*/        return dfs(grid,row-1,col-1);    }    public int dfs(int a[][],int i,int j){
     //记忆化        if(i < 0 || j < 0) return 0;        if(dp[i][j]>=0) return dp[i][j];  //已经计算过了不需要再算        else dp[i][j]=Math.max(dfs(a,i,j-1),dfs(a,i-1,j))+a[i][j];        return dp[i][j];    }}

转载地址：https://dh-butterfly.blog.csdn.net/article/details/108418298 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！