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

主要思想： 因为只能向右移动和向下移动 到达位置[i][j]的最小路径和一定是到达它左边位置[i][j-1]的路径和到达它上边位置[i-1][j]的路径和中最小的路径和再加上[i][j]的数。 即状态转移方程为： dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i,j];

#include<vector>
using namespace std;
int minSum(vector<vector<int>>& m,int r,int c){
    for(int i=0;i<m.size();i++){
        for(int j=0;j<m[0].size();j++){
            if(i==0&&j==0) continue;
            if(i==0&&j!=0){
                 m[i][j]+=m[i][j-1];
                continue;
            }
            if(i!=0&&j==0){
                 m[i][j]+=m[i-1][j];
                continue;
            }
            m[i][j]+=min(m[i-1][j],m[i][j-1]);
        }
    }
    return m[r-1][c-1];
}
int main(){
    int row=0;
    int col=0;
    cin>>row;
    cin>>col;
    vector<vector<int>> m(row,vector<int>(col,0));
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cin>>m[i][j];
        }
    }
    cout<<minSum(m,row,col);
    return 0;
}