题解 | #矩阵的最小路径和#
矩阵的最小路径和
http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
/*第一种方法：申请二维数组dp[row][col]，空间复杂度为O(mn)
int minPathSum(vector<vector<int> >& matrix) {
// write code here
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int>> dp(row, vector<int>(col));
dp[0][0] = matrix[0][0];
for (int i = 1; i < row; i ++) {
dp[i][0] = dp[i - 1][0] + matrix[i][0];
}
for (int i = 1; i < col; i ++) {
dp[0][i] = dp[0][i - 1] + matrix[0][i];
}
for (int i = 1; i < row; i ++) {
for (int j = 1; j < col; j ++) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + matrix[i][j];
}
}
return dp[row - 1][col - 1];
}*/
//第二种方法：思路一模一样，不过是在原数组上更改，空间复杂度为O(1)
int minPathSum(vector<vector<int> >& matrix) {
int row = matrix.size();
int col = matrix[0].size();
for (int i = 1; i < row; i ++) {
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
for (int i = 1; i < col; i ++) {
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
for (int i = 1; i < row; i ++) {
for (int j = 1; j < col; j ++) {
matrix[i][j] = min(matrix[i][j - 1], matrix[i - 1][j]) + matrix[i][j];
}
}
return matrix[row - 1][col - 1];
}
};
