题解 | 矩阵的最小路径和

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int a[2005][2005];
int dp[2005][2005];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        cin>>a[i][j];
        }
    }
    dp[1][1]=a[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        if(i==1)dp[i][j]=dp[i][j-1]+a[i][j];
        else if(j==1)dp[i][j]=dp[i-1][j]+a[i][j];
        else dp[i][j]=min(dp[i][j-1],dp[i-1][j])+a[i][j];
        }

    }
    cout<<dp[n][m];
    return 0;
}
//乍一看和上一道三角形一样，也是路径转移，找最值路径和，那么到底是不是呢，不知道，看一看。左上角出发只能向右或向下，没有斜着走。因此可以先列出一个dp[i][j]=min(dp[i][j-1],dp[i-1][j])+a[i][j];如果这么想就错了，动态规划转移时一定要牢记边界问题，边界的点显然只能从上方转移和左方转移选择其一。于是条件判断求解，记得初始化哟

乍一看和上一道三角形一样，也是路径转移，找最值路径和，那么到底是不是呢，不知道，看一看。左上角出发只能向右或向下，没有斜着走。因此可以先列出一个dp[i][j]=min(dp[i][j-1],dp[i-1][j])+a[i][j];如果这么想就错了，动态规划转移时一定要牢记边界问题，边界的点显然只能从上方转移和左方转移选择其一。于是条件判断求解，记得初始化哟