题解 | #矩阵的最小路径和#

#include <iostream>
#include <cstring>
using namespace std;
const int N = 501;
int map[N][N];
int dp[N][N]; //其中 dp[i][j]表示  到位置(i,j)时的最小路径和

int main() {

    int n, m;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j] = 500000;
        }
    }
    //cout << "tet = " << dp[0][1] << endl;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    //cout << "n= " << n << " m= " << m << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                dp[i][j] = map[i][j];
                continue;
            }
            //从哪里来
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + map[i][j];
            //cout << "i=" << i << " j= " << j << " dp[i][j]= " << dp[i][j] << endl;
        }

    printf("%d", dp[n][m]);

    return 0;
}
// 64 位输出请用 printf("%lld")