这个题虽然是 中等的动态规划题,确实简单。简单在于状态转移方程只有四种情况。
默认当前位置的价值为当前礼品的价值。
1.如果当前位置行列数都大于0,当前位置的价值需加上左边位置跟上边位置的最大值
2.如果当前位置只有行数大于0,当前位置的价值需加上上边位置的值
3.如果当前位置只有列数大于0,当前位置的价值需加上左边位置的值
4.当前位置在左上角,价值不变。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> * @return int整型 */ int maxValue(vector<vector<int> >& grid) { // write code here int m = grid.size(); if(m == 0){ return 0; } int n = grid[0].size(); vector<vector<int> >dp = vector<vector<int> > (m,vector<int>(n,0)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dp[i][j] = grid[i][j]; if(i > 0 && j > 0){ dp[i][j] += max(dp[i][j-1],dp[i-1][j]); }else if(i>0){ dp[i][j] += dp[i-1][j]; }else if(j>0){ dp[i][j] += dp[i][j-1]; } } } return dp[m-1][n-1]; } };