面试题47. 礼物的最大价值(简单)

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

示例 1:

输入: 

1
2
3
4
5
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof

思路1：

明显是dp，转移方程为
$$
d p(i, j)=\left{\begin{array}{ll}
\operatorname{grid}(i, j) & , i=0, j=0 \
\operatorname{grid}(i, j)+d p(i, j-1) & , i=0, j \neq 0 \
\operatorname{grid}(i, j)+d p(i-1, j) & , i \neq 0, j=0 \
\operatorname{grid}(i, j)+\max [d p(i-1, j), d p(i, j-1)] & , i \neq 0, j \neq 0
\end{array}\right.
$$

  1. 当i=0且j=0时，为起始元素
  2. 当i=0且j!=0时，为矩阵第一行元素，只能从左边到达
  3. 当i!=0且j=0时，为矩阵第一列元素，只能从上边到达
  4. 当i!=0且j!=0时，可从左边或上边到达

本思路代码为代码1，使用了二维数组，空间复杂度为O(mn)

思路2：

可以将用滚动数组将空间复杂度，优化成O(n)，不过这个思路我并不是很理解，虽然很常见，但是不是很好用上

使用一位数组即可，代码为代码2

思路3：

由于 dp[i] [j]dp[i] [j] 只与 dp[i-1] [j]dp[i−1] [j] , dp[i] [j-1]dp[i] [j−1] , grid[i] [j]grid[i] [j] 有关系，因此可以将原矩阵 grid 用作 dp 矩阵，即直接在 grid 上修改即可。
应用此方法可省去 dp 矩阵使用的额外空间，因此空间复杂度从 O(MN) 降至 O(1)。

作者：jyd
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/solution/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxValue(int[][] grid) {
        //明显dp
        //f(i,j)= max{f(i-1,j),f(i,j-1)}+grid[i][j]
        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 &&j==0)//如果在起点
                    dp[i][j]=grid[i][j];
                else if(i==0)//如果是第一行
                    dp[i][j] = dp[i][j-1]+grid[i][j];
                else if(j==0)//如果是第一列
                    dp[i][j] = dp[i-1][j]+grid[i][j];
                else 
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];

            }
        }
        return dp[m-1][n-1];
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
            } 
        }

        return dp[n];
    }
}

代码3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int maxValue(int[][] grid) {
        //明显dp
        //f(i,j)= max{f(i-1,j),f(i,j-1)}+grid[i][j]
        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        //int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 &&j==0)//如果在起点
                    // dp[i][j]=grid[i][j];
                    continue;
                else if(i==0)//如果是第一行
                    grid[i][j] += grid[i][j-1];
                    // dp[i][j] = dp[i][j-1]+grid[i][j];
                else if(j==0)//如果是第一列
                    grid[i][j] += grid[i-1][j];
                    // dp[i][j] = dp[i-1][j]+grid[i][j];
                else 
                    grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);

            }
        }
        return grid[m-1][n-1];
    }
}