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

描述 给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: 1≤n,m≤5001 \le n,m\le 5001≤n,m≤500，矩阵中任意值都满足 0≤ai,j≤1000 \le a_{i,j} \le 1000≤ai,j​≤100 要求：时间复杂度 O(nm)O(nm)O(nm)

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12， 所选择的最小累加和路径如下图所示：

输入描述： 第一行输入两个正整数 n 和 m 表示矩阵 a 的长宽 后续输入 n 行每行有 m 个数表示矩阵的每个元素 输出描述： 输出从左上角到右下角的最小路径和

示例1 输入：

4 4 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0

输出：

12

示例2 输入：

2 3 1 2 3 1 2 3

输出：

7

#include <vector>

using namespace std;
class Solution{
    
    
    
public:
    
    int minDistance(vector<vector<int>> &grid){
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        int isum =0;
        int jsum = 0;
        for (int i = 0;i<m;i++){
            isum += grid[i][0];
            dp[i][0] = isum;
        }
        
        for (int j = 0;j<n;j++){
            jsum += grid[0][j];
            dp[0][j] = jsum;
        }
        
        for (int i =1;i<m;i++){
            for (int j =1;j<n;j++){
                dp[i][j] = min (dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        
        return dp[m-1][n-1];
        
        
    }
};
int main(){
    
    Solution solu;
    
    int n,m,val;
    cin >> n >> m;
    
    vector<vector<int>>grid(n,vector<int>(m));
    for (int i =0;i<n;i++){
        for (int j =0;j<m;j++){
            cin >> val;
            grid[i][j] = val;
        }
    }
    
    cout<< solu.minDistance(grid) <<endl;
    
    return 0;
}