[数据结构与算法]剑指 Offer 47. 礼物的最大价值

求最值 动态规划，遍历

动态规划需要定义状态，以及会改变状态的选择

dp[i][j] 表示移动到 [i][j]位置时所获礼物的最大价值，选择的话就是每次向右或者向下移动一格，base case就是第一列和第一行的价值是从第一个格子开始累加到当前格子的值

芜湖，手写的dp，一遍ac

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int row = grid.size();
        int column = grid[0].size();
        vector<vector<int>> dp(row, vector(column, 0));
        int sum = 0;
        for( int j = 0; j < column; j++ ){
            dp[0][j] = sum + grid[0][j];
            sum += grid[0][j];
        }
        sum = 0;
        for( int i = 0; i < row; i ++ ){
            dp[i][0] = sum + grid[i][0];
            sum += grid[i][0];
        }
        for( int i = 1; i < row; i ++ ){
            for( int j = 1; j < column; j++ ){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
};