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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    //本题经典的动态规划题目
    //定义一个和棋盘一样大的二维数组dp
    //dp[i][j]的含义为从最左上角来到这个i，j位置能获得的最大价值为dp[i][j]
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        if(grid.size()==0||grid[0].size()==0){
            return 0;
        }
        int m=grid.size();
        int n=grid[0].size();
        int dp[m][n];//定义一个m行n列的dp数组
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=0;//初始化为0
            }
        }
        dp[0][0]=grid[0][0];//第一个位置的最大价值肯定是grid[0][0]的值
        //对于第dp一行和第一列的值来说，因为每次只能向右或者向下移动，所以第一行第一列的值很好求
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int j=1;j<m;j++){
            dp[j][0]=dp[j-1][0]+grid[j][0];
        }
        //除了第一行第一列以外的位置，可以来自上方和左边
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};