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

class Solution {

public:

    /**

     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     *

     * 

     * @param grid int整型vector<vector<>> 

     * @return int整型

     */

    int maxValue(vector<vector<int> >& grid) {

        // write code here

        int m=grid.size();         //行数m

        int n=grid[0].size();         //列数n

        int rec[m][n];               //记录最大值的二维数组rec，这里空间复杂度高一些

        rec[0][0]=grid[0][0];     //初始化左上角rec

        for(int i=1;i<m;i++){         //填补rec的第一列

            rec[i][0]=rec[i-1][0]+grid[i][0];

        }

        for(int i=1;i<n;i++){        //填补rec的第一行

            rec[0][i]=rec[0][i-1]+grid[0][i];

        }

        for(int i=1;i<m;i++){        //找剩下的rec空的地方的最大值，遍历一遍

            for(int j=1;j<n;j++){

                rec[i][j]=max(rec[i-1][j],rec[i][j-1])+grid[i][j];

            }

        }

        return rec[m-1][n-1];

    }

};