# 面试刷题-动态规划-求解最短路径

#### 题目描述

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输入：grid = [[1,2,3],[4,5,6]]

#### 实现代码

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
std::vector<std::vector<int> > sum(row, std::vector<int>(col, 0));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 && j == 0) {
sum[i][j] = grid[i][j];
} else if (i == 0 && j > 0) {
sum[i][j] = sum[i][j - 1] + grid[i][j];
} else if (i > 0 && j == 0) {
sum[i][j] = sum[i - 1][j] + grid[i][j];
} else {
sum[i][j] = std::min(sum[i][j - 1] + grid[i][j], sum[i - 1][j] + grid[i][j]);
}
}
}
return sum[row - 1][col - 1];
}
};

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int rows = grid.size(), columns = grid[0].size();
auto dp = vector < vector <int> > (rows, vector <int> (columns));
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
};

#### 优化空间复杂度到O(n)的代码实现:

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int rows = grid.size();
int columns = grid[0].size();
auto dp = vector<int>(columns);
dp[0] = grid[0][0];
for (int i = 1; i < columns; i++) {
dp[i] = dp[i - 1] + grid[0][i];
}
for (int j = 1; j < rows; j++) {
dp[0] = dp[0] + grid[j][0];
for (int k = 1; k < columns; k++) {
dp[k] = std::min(dp[k] + grid[j][k], dp[k - 1] + grid[j][k]);
}
}
return dp[columns - 1];
}
};