题解 | #礼物的最大价值#
礼物的最大价值
http://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134
这个题虽然是 中等的动态规划题，确实简单。简单在于状态转移方程只有四种情况。
默认当前位置的价值为当前礼品的价值。
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];
}
};
投递淘天集团等公司10个岗位
查看9道真题和解析