这个题虽然是 中等的动态规划题,确实简单。简单在于状态转移方程只有四种情况。
默认当前位置的价值为当前礼品的价值。
1.如果当前位置行列数都大于0,当前位置的价值需加上左边位置跟上边位置的最大值
2.如果当前位置只有行数大于0,当前位置的价值需加上上边位置的值
3.如果当前位置只有列数大于0,当前位置的价值需加上左边位置的值
4.当前位置在左上角,价值不变。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m = grid.size();
        if(m == 0){
            return 0;
        }
        int n = grid[0].size();
        vector<vector<int> >dp = vector<vector<int> > (m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j] = grid[i][j];
                if(i > 0 && j > 0){
                    dp[i][j] += max(dp[i][j-1],dp[i-1][j]);
                }else if(i>0){
                    dp[i][j] += dp[i-1][j];
                }else if(j>0){
                    dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};