题解 | 矩阵的最小路径和

到达出口只能从出口左边或者上边来，这样就很容易写出递归式,并且进行记忆化搜索。也可以使用状态方程dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j] 进行递推，处理好边界即可。

#include<bits/stdc++.h>
using namespace std;
int solve(int i, int j, vector<vector<int>> &v, vector<vector<int>> &dp){
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 && j == 0) {
        dp[i][j] = v[i][j];
        return dp[i][j];
    } 
    else if(i == 0){
        dp[i][j] = solve(i, j-1, v, dp) +v[i][j];
        return dp[i][j];
    }
    else if(j == 0){
        dp[i][j] = solve(i-1, j, v, dp) + v[i][j];
        return dp[i][j];
    }
    else{
        dp[i][j] = min(solve(i-1,j,v,dp), solve(i, j-1, v, dp)) + v[i][j];
        return dp[i][j];
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    vector<vector<int>> v(n,vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m, -1));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin>>v[i][j];
        }
    }
    cout<<solve(n-1,m-1,v,dp)<<endl; 
    return 0;
}