题解 | #礼物的最大价值#

• 动态规划，定义dp数组大小为m*n（与grid大小一致），记录当前最大值；
• 初始化，dp[0][0]为grid[0][0]，第一行和第一列为该行和该列的累加值；
• 只能向下或向右移动，确定递推关系：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]；
• 遍历完成，返回最终结果。

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