剑指 Offer 47 礼物的最大价值

概述

https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

动态规划法

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        vector<vector<int>> dp = grid;
        for (int r = grid.size() - 1; r >= 0; r --) {
            for (int c = grid[0].size() - 1; c >= 0; c --) {
                if (r != grid.size() - 1) {
                    dp[r][c] = max(dp[r][c], grid[r][c] + dp[r+1][c]);
                }
                if (c != grid[0].size() - 1) {
                    dp[r][c] = max(dp[r][c], grid[r][c] + dp[r][c+1]);
                }
            }
        }
        return dp[0][0];
    }
};