题解 | 矩阵的最小路径和

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        vector<vector<int>> arr(a,vector(b,0));
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                cin>>arr[i][j];
            }
        }
        vector<vector<int>> dp(a,vector(b,0));
        dp[0][0]=arr[0][0];
        for(int i=1;i<a;i++){
            dp[i][0]=dp[i-1][0]+arr[i][0];
        }
        for(int j=1;j<a;j++){
            dp[0][j]=dp[0][j-1]+arr[0][j];
        }
        for(int i=1;i<a;i++){
            for(int j=1;j<b;j++){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j];
            }
        }
        std::cout<<dp[a-1][b-1];
        return 0;
    }
}
// 64 位输出请用 printf("%lld")