礼物的最大价值（C++）

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

如输入这样的一个二维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]

那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12

输入：
[[1,3,1],[1,5,1],[4,2,1]]
返回值：
12

备注：

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

使用动态规划算法，建立二维数组dp用于保存当前位置的最大价值。其状态转移方程为dp[i][j] = dp[i-1][j] > dp[i][j-1]?dp[i-1][j]+grid[i][j]:dp[i][j-1]+grid[i][j];表示第i行第j列位置的最大价值等于左边和上方的最大值加上当前位置的价值之和。

class Solution {
public:
    
    int maxValue(vector >& grid) {
        vector> dp(grid.size(),vector(grid[0].size(),0));
        //dp数组初始化，第一行和第一列，由于第一行和第一列不需要进行比较，仅仅等于当前位置前面的数累加和。
        dp[0][0] = grid[0][0];
        for(int i = 1;i dp[i][j-1]?dp[i-1][j]+grid[i][j]:dp[i][j-1]+grid[i][j];
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

优化算法：

int maxValue(vector >& g) {
        int dp[1000][1000]{0};
        dp[1][1]=g[0][0];
        int n=g.size();
        int m=g[0].size();
        for(int i=0;i
            for(int j=0;j
                int x=i+1,y=j+1;
                dp[x][y]=max(dp[x-1][y],dp[x][y-1])+g[i][j];
            }
        }
        return dp[n][m];
    }

使用dfs深度优先算法进行深度遍历，但是时间超时，仅供参考。

class Solution {
  public:
    
    int res = 0;
    int maxValue(vector >& grid) {
        dfs(grid, 0, 0, 0);
        return res;
    }
    void dfs(vector >& grid, int x, int y, int sum)     {
        if (x == grid.size() && y == grid[0].size()) {
            res = max(res, sum);
            return;
        } else if (x == grid.size()) {
            dfs(grid, x, y + 1, sum);
        } else if (y == grid[0].size()) {
            dfs(grid, x + 1, y, sum);
        } else {
            dfs(grid, x + 1, y, sum + grid[x][y]);
            dfs(grid, x, y + 1, sum + grid[x][y]);
        }
        return;
    }
};