面试题47：礼物的最大价值（C++）

题目地址：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

题目描述

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

题目示例

示例 1:

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

解题思路

动态规划：声明二维数据dp表示礼物的最大价值，其中，状态表示dp[i][j]为到达i,j位置处的最大价值，转移方程为dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j]。因为出发的方向只能是向下或者向右，所以第一行或者第一列的礼物最大价值dp等于当前礼物价值+上一个dp值。为了简便，我们先初始化第一行和第一列，然后从第二行和第二列开始遍历。

矩阵法：思想与动态规划思想一样，不过需要注意的是矩阵法要判断边界，防止溢出。深度优先搜索DFS 或广度优先搜索 BFS 强调”朝某方向“搜索，因此在撞到边界时（越界时），就应返回，我们称之为剪枝，而动态规划则是直接遍历列表或者矩阵，使用转移方程计算dp列表中的值，因此就没有越界。

动态规划优化：观察状态转移方程，可以发现j只与当前位置j和前一个位置j-1有关，考虑将二维数组dp优化为一维数组，因为当前的状态只与上一个状态有关，使用一维数组dp保存上一行的最大价值，所以我们只需要更新dp即可，状态转移方程变为dp[j] = max(dp[j],dp[j-1]) + grid[i][j]。

程序源码

动态规划

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() == 0) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        dp[0][0] = grid[0][0]; //初始化礼物最大价值
        for(int i = 1; i < rows; i++)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0]; //向下
        }
        for(int j = 1; j < cols; j++)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j]; //向右
        }
        for(int i = 1; i < rows; i++)
        {
            for(int j = 1; j < cols; j++)
            {
                dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1]); //坐标(i,j)处得到最大价值礼物
            }
        }
        return dp[rows - 1][cols - 1]; //返回礼物最大价值
    }
};

矩阵法

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() == 0) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; 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] += max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[rows - 1][cols - 1]; //最大价值礼物
    }
};

动态规划优化

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() == 0) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<int> dp(cols + 1, 0);
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
            {
                dp[j + 1] = max(dp[j], dp[j + 1]) + grid[i][j];
            }
        }
        return dp[cols];
    }
};