题解 | 礼物的最大价值

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
     
    int recursion(vector<vector<int> >& grid, int row, int line, vector<vector<int> >& dp){
        if(row==0&&line==0){
            dp[0][0] = grid[0][0];
            return dp[0][0];
        }
        
        if(row==0)
            dp[0][line] = grid[0][line] + recursion(grid, row, line-1, dp);
        if(line==0)
            dp[row][0] = grid[row][0] + recursion(grid, row-1, line, dp);
        if(dp[row][line]==0)
            dp[row][line] = grid[row][line] + max(recursion(grid, row-1, line, dp), recursion(grid, row, line - 1, dp));
            return dp[row][line];
    }
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m = grid.size(), n = grid[0].size();
        vector<vector<int> > dp(m, vector<int>(n, 0));
        return recursion(grid, m-1, n-1, dp);
    }
};

dfs能过一部分，但是dfs在这个里的很大问题就是重复计算，所以我们需要通过记忆化的方法剪枝。

如果是从小到大的话不能剪枝，因为不同来路到同一个点的之前积累不同，所以只能从后往前。

所以我们从最后的结尾开始看来路，从左从上，比较最大的，然后给这个位置。

直到最后到了(0, 0)点，作为初始点给值。

当然从前往后也有一种解法，就是全部按顺序跑一遍，这样不重不漏。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        if(grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int> > dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for(int i = 1; i < n; ++i){
            dp[0][i] = grid[0][i] + dp[0][i-1];
        }
        for(int i = 1; i < m; ++i){
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                dp[i][j] = grid[i][j]+max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
};

这个就是考虑怎么不重不漏，要从哪个方向开始就不会漏和重复，这里是左上角来的，所以左和上都有了生成其他的就不会有问题。