Maximum value of jz47 gifts (dynamic planning ideas)

The key of dynamic programming is , seek dp Equation of state , Compare the results with dp State binding , The solving problem is divided into several sub problems , So as to solve the result

For the whole process , Let's consider the special situation first , That is, gifts are only along the first 0 OK or the second 0 The column moves , So the gift value grid[i][j]+=grid[i][j-1] perhaps grid[i][j]+=grid[i-1][j], In other cases grid[i][j]+=max(grid[i][j-1],grid[i-1][j])

The code is as follows

    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];
    }
};