二维矩阵从左上角到右下角路径的最小和-动态规划
牛妹的礼物
http://www.nowcoder.com/questionTerminal/c4f777778e3040358e1e708750bb7fb9
一、思路：
用一个矩阵dp来保存走到每个格子的时候，当前格子累计的礼物的最小体积，dp的大小和格子的大小一致，也是N*M的矩阵。
二、图示：
1、dp第0行和第0列的初始化；
2、dp的更新，注意题目中要求只能想右、下、右下角走。所以dp[i][j]是它的左上角、上、左，三个值中最小的一个，再加上当前格子的礼物体积：
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])) + presentVolumn[i][j];
3、返回值是dp最右下角的值。
四、代码：
class Solution {
public:
/**
*
* @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
int selectPresent(vector<vector<int> >& presentVolumn) {
int h = presentVolumn.size();
if(h == 0)
return 0;
int w = presentVolumn[0].size();
if(w == 0)
return 0;
vector<vector<int>> dp(h, vector<int>(w));
//初始化第0行
dp[0][0] = presentVolumn[0][0];
for(int i = 1; i < w; i++)
dp[0][i] = dp[0][i-1] + presentVolumn[0][i];
//初始化第0列
for(int i = 1; i < h; i++)
dp[i][0] = dp[i-1][0] + presentVolumn[i][0];
//计算内部值
for(int i = 1; i < h; i++){
for(int j = 1; j < w; j++){
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + presentVolumn[i][j];
}
}
return dp[h-1][w-1];
}
}; 
查看34道真题和解析
