动态规划

• 找出最佳路径，不能只比较右边和下边的项来来确定最大值，局部最佳!=全局最佳。
• 矩阵的第一行和第一列的路径礼物价值是确定的，(只能向右|下)。
• grid[i][j]= grid[i][j]=max(grid[i-1][j] ,grid[i][j-1])+grid[i][j]; 计算出到达i,j路径的最优解
• 理解只能向右或者向下，向右/下决定哪些行和列的路径礼物价值确定+max考虑的上一个位置

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

        }
        for(int i=0;i<grid.size();i++)
        {
            for(int j=1;j<grid[0].size();j++)
            {
                if(i==0)
                {
                    grid[i][j]=grid[i][j-1]
                    +grid[i][j];
                }
                else{
                    grid[i][j]=max(grid[i-1][j]
                    ,grid[i][j-1])+grid[i][j];
                }
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }
};