jz47 礼物的最大价值（动态规划思路）

动态规划问题的关键是，寻找dp状态方程，将结果与 dp状态绑定起来,将求解问题划分为若干个子问题，从而求解出结果

对于整个过程，我们先考虑特殊情况，即礼物只沿第0行或者第0列移动，那么礼物价值grid[i][j]+=grid[i][j-1]或者grid[i][j]+=grid[i-1][j],其他情况下 grid[i][j]+=max(grid[i][j-1],grid[i-1][j])

代码如下

    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int col=grid[0].size();
        int row=grid.size();
        if(row==0)
            return 0;

        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
                if(j>0&&i>0)
                    grid[i][j]+=max(grid[i-1][j],grid[i][j-1]);
                else if(j>0)
                    grid[i][j]+=grid[i][j-1];
                else if(i>0)
                    grid[i][j]+=grid[i-1][j];
            }
        return grid[row-1][col-1];
    }
};