1. 剑指offer-JZ47-路径问题-礼物的最大价值

题目链接：

礼物的最大价值_牛客题霸_牛客网https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134?tpId=265&tqId=39288&ru=/exam/oj

 

---

 2.  算法原理 

状态表示：以莫一个位置位置为结尾

    

dp[i，j]表示：走到[i，j]位置的时候，此时能拿到礼物的最大价值

2. 状态转移方程

  

根据最近的一步来划分问题：

      

到达dp[i][j]有两种情况：

                                         1. 从上面过来：dp[i-1，j] -> dp[i，j]，dp[i-1，j] + g[i][j]

        

                                         2. 从左边过来：dp[i，j-1] -> dp[i，j]，dp[i，j-1] + g[i][j]

    

从起始位置到从上/左（dp[i-1，j] /dp[i，j-1]）的最大价值的值加上最后目的地的值

    
本题的状态转移方程是：dp[i][j] = max(dp[i-1，j] ,dp[i，j-1])+ g[i][j]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

   

我们可以在上面的一行和左边的一列再额外的加上一行和一列的虚拟节点

   

因为本题是两值相比最大价值的值加上后面的值再继续进行，所以我们定义的虚拟节点的值是不能影响原矩阵的值的，而题目要求值的大小不能小于0，那么我们把虚拟节点的值设为0，两个位置（虚拟节点和原始矩阵）取最大值时虚拟节点一定不会被选上

    

   

本题的下标映射关系：因为本题给了一个矩阵，而我们又额外的加上一行和一列的虚拟节点，所以我们的下标都统一往右下角移动了一位，如果想找回之前对应的位置，那么下标需要进行统一减1（横纵坐标）

4. 填表顺序 

    

本题的填表顺序是：从上往下填写每一行，每一行的值是从左往右

5. 返回值 ：题目要求 + 状态表示 

    

本题的返回值是：dp[m][n]

 

---

3.代码

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值 

class Solution {
public:

    int maxValue(vector<vector<int> >& grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 1));
        //额外的加上一行和一列的虚拟节点，所以从1开始
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                //这里的grid[i-1][j-1]也是加上一行和一列的虚拟节点，所以要横纵-1
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

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

---

感谢观看~