题解 | #矩阵的最小路径和#
矩阵的最小路径和
https://www.nowcoder.com/practice/38ae72379d42471db1c537914b06d48e
求最优解，使用动态规划。
dp[i][j]代表从坐标（0,0）到坐标（i，j）的最小路径和。
1）边界条件：
dp[0][0] = 0
矩阵的上侧边和左侧边上最小路径和是固定的
dp[i][0] = dp[i-1][0] + nums[i][0] //只能向右移动
dp[0][j] = dp[0][j-1] + nums[0][j] //只能向下移动
2)状态转移方程
向右
dp[i][j] = dp[i-1][j] + nums[i][j]
向下
dp[i][j] = dp[i-1][j] + nums[i][j]
最小路径和，即取以上两个方向的最小值
min(dp[i-1][j] + nums[i][j]， dp[i-1][j] + nums[i][j])
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int m;
int n;
while (cin >> n && cin >> m) {
vector<vector<int>> dp(n, vector<int>(m, 0));
vector<vector<int>> nums(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> nums[i][j];
}
}
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0) {
dp[i][j] = dp[0][j-1] + nums[i][j];
}else if (j == 0){
dp[i][j] = dp[i-1][0] + nums[i][j];
} else {
dp[i][j] = min(dp[i-1][j]+nums[i][j], dp[i][j-1]+nums[i][j]);
}
}
}
cout << dp[n-1][m-1] <<endl;
}
}
