C++ 代码

/*
dp[i][j]:表示到(i,j)这个点礼物最大的

dp[i][j]=max(dp[i][j-1],dp[i-1][j])+grid[i][j]

*/
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        //这个题一看就是dp
        if(grid.empty()){
            return 0;
        }
        int rows=grid.size(),cols=grid[0].size();
        vector<vector<int>> dp(rows,vector<int>(cols,0));
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(i==0){
                    if(j==0){
                        dp[i][j]=grid[0][0];
                    }else{
                        dp[i][j]=dp[i][j-1]+grid[i][j];
                    }
                }else if(j==0){
                    if(i==0){
                        dp[i][j]=grid[0][0];
                    }else{
                        dp[i][j]=dp[i-1][j]+grid[i][j];
                    }
                }
                else{
                     dp[i][j]=max(dp[i][j-1],dp[i-1][j])+grid[i][j];
                }
        }

        }
        return dp[rows-1][cols-1];

    }
};