题解 | 矩阵的最小路径和

只需要每次把数字左边和数字上面的两个数字取最小的一个即可(数字只能从这两个方向移动)。

如果另外开一个dp数组大概率存不下。

所以直接操作原数组，注意边界位置，样例结果为11的就是忘记处理第一行和第一列了。

状态转移方程：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + v[i][j]

最后一个格子(n,m)为最短路径和的结果

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>> v(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int t;
            cin>>t;
            if(i==1){
                v[i][j]=t+v[i][j-1];
                continue;
            }
            if(j==1){
                v[i][j]=t+v[i-1][j];
                continue;
            }
            v[i][j]=min(v[i][j-1],v[i-1][j])+t;
        }
    }
    cout<<v[n][m];
}