一、题目
二、思路
基础题。拿到题目，“最大价值”、路线问题，可以发现和以前做的【LeetCode62】不同路径（dp）是一个思路的，都是规定从左上角，每次只能向右or向下移动一格，于是那题从当前状态考虑时，需要将上方格子的dp值和左方的dp值相加（因为那里是求路径方法数），但是本题是取max（因为这里是求一条路径，该路径使得礼物价值最大）。
（1）确定状态
状态f ( i , j ) f(i, j)f(i,j)表示到达当前( i , j ) (i, j)(i,j)坐标位置时能够拿到的礼物最大总和。
（2）状态转移方程
其中g ( i , j ) g(i, j)g(i,j)是当前格子的礼物价值。
（3）边界+初始条件
dp[o][0]，还有第一列和第一行的dp值。
（4）计算顺序
计算下标i时的数据需要有i-1时的数据，所以从小到大遍历i和j。
三、代码
class Solution { public: int maxValue(vector<vector<int>>& grid) { //dp[i][j]表示目前到该位置的最大价值 int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = grid[0][0]; for(int i = 1; i < n; i++){ dp[0][i] = dp[0][i - 1] + grid[0][i]; } for(int j = 1; j < m; j++){ dp[j][0] = dp[j - 1][0] + grid[j][0]; } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; } } return dp[m - 1][n - 1]; } };
由于每次在[i][j]位置时只用到上方和左方的格子数据，所以还可通过【滚动数组】进行空间复杂度上的优化，这里贴一个《剑指offer》优化解法：
#include <vector> #include <iostream> #include <string> #include <string.h> #include <algorithm> using namespace std; int getMaxValue(const int *val,int rows,int cols){ if((val == NULL)||(rows <= 0)||(cols <= 0))return 0; //只用一行缓存来缓存上一行的最大值 int *buffer = new int[cols]; for(int i = 0;i != rows;i++){ for(int j = 0;j != cols;j++){ int up = 0,left = 0; //取上面一格的最大值 if(i != 0){ up = buffer[j]; } //因为左边一格的最大值会及时更新到缓存，所以这里取的是左边一格的数据 if(j != 0){ left = buffer[j-1]; } int tmp = max(up,left)+val[i*cols+j]; //对当前行的数据实时更新到缓存 buffer[j] = tmp; } } int resu = buffer[cols-1]; delete[] buffer; return resu; } int main(){ int *test = new int[16]; test[0] = 1; test[1] = 10; test[2] = 3; test[3] = 100; test[4] = 12; test[5] = 2; test[6] = 9; test[7] = 6; test[8] = 5; test[9] = 7; test[10] = 4; test[11] = 11; test[12] = 3; test[13] = 7; test[14] = 16; test[15] = 5; cout << getMaxValue(test,4,4) << endl; return 0; }
