Leetcode 最小路径和

Question

我正在研究一个叫做最小路径总和的问题。我已经制定了我的逻辑并发现它是正确的，但我在代码中遇到运行时错误。我已经正确搜索但找不到任何错误。这是代码：-

  class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
       int colsize=grid.size();
        int rowsize=grid[0].size();
       for(int i=1;i<rowsize;i++)
       {
           grid[0][i]+=grid[0][i-1];
       }
       for(int i=1;i<colsize;i++)
       {
           grid[i][0]+=grid[i-1][0];
       }

        for(int i=1;i<rowsize;i++)
        {
            for(int j=1;j<colsize;j++)
            {
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[rowsize-1][colsize-1];
       
        
    }
};

和问题的 link https://leetcode.com/problems/minimum-path-sum/

对于测试用例：-

[[1,2,3],[4,5,6]]

运行时出错。

Answer 1

看来你在问题的后半部分不小心调换了 colsize 和 rowsize:

        for(int i=1;i<rowsize;i++)
        {
            for(int j=1;j<colsize;j++)
            {
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[rowsize-1][colsize-1];

应该是：

        for(int i=1;i<colsize;i++)
        {
            for(int j=1;j<rowsize;j++)
            {
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[colsize-1][rowsize-1];

因为colsize用作第一个索引的限制，rowsize用作第二个索引的限制。

Leetcode 最小路径和

Leetcode Minimum Path Sum

c++

dynamic-programming