题目描述：

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

寻路算法，要求最短路径反过来，代价最高的路径

暴力一点，我直接DFS所有路径走一遍，但是显然不需要，太复杂了，我要找的是价值最高的路径

比如同样是到斜右下方的点，可以从下去，也可以右边，看哪个大走哪边

这一题是否可以用动归？我就维护从起点到我这里，最长的路怎么走，而到我这只有两种可能，一种是从我左边，一种是从我上边来，那左边和上边其实已经有各自的最大解，那我只需要考虑我加上左边和上边的礼物价值后，哪个最大，然后保留最大的那个方案，以供后续节点挑选

算法实现：

  1. class Solution {
  2. public:
  3.     int maxValue(vector<vector<int>>& grid) {
  4.         int m = grid.size();
  5.         int n = grid[0].size();
  6.         vector<vector<int>> DP(m+1,vector<int> (n+1,0));
  7.         for(int i=1;i<m+1;i++){
  8.             for(int j=1;j<n+1;j++){
  9.                 DP[i][j] = max(DP[i-1][j],DP[i][j-1])+grid[i-1][j-1];
  10.             }
  11.         }
  12.         return DP[m][n];
  13.     }
  14. };

复杂度分析：

image.png
一个二维的DP数组需要维护，维护的过程是双层循环
O(n^2)

所以可以优化的点在于，我走到目前这一步了，除了前一层的对我有用，前几层的都没啥用，所以可以将输入的这个矩阵本身用作一个DP求解记录空间，

  1. class Solution:
  2.     def maxValue(self, grid: List[List[int]]) -> int:
  3.         for i in range(len(grid)):
  4.             for j in range(len(grid[0])):
  5.                 if i == 0 and j == 0: continue
  6.                 if i == 0: grid[i][j] += grid[i][j - 1]
  7.                 elif j == 0: grid[i][j] += grid[i - 1][j]
  8.                 else: grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
  9.         return grid[-1][-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/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。