Unexpected result from LeetCode (Minimum Path Sum)

Question

I used an online compiler to test my code, and it runs correctly. However, when I submit my code to LeetCode, it always returns a random negative number, like -1218055056.

The problem description is as below,

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

And my code is as below,

class Solution {
public:
    int sub(vector<vector<int> >& grid, int** dp, int m, int n) {
        if(dp[m][n] == 0) {
            if(m==0 && n==0) {
                *(*(dp+m)+n) = grid.at(m).at(n);
            } else {
                if(m == 0) {
                    *(*(dp+m)+n) = sub(grid, dp, m, n-1);
                } else if(n == 0) {
                    *(*(dp+m)+n) = sub(grid, dp, m-1, n);
                } else {
                    int left = sub(grid, dp, m, n-1);
                    int up = sub(grid, dp, m-1, n);
                    
                    *(*(dp+m)+n) = left<up?grid.at(m).at(n)+left:grid.at(m).at(n)+up;
                }
            }
        }
        
        return *(*(dp+m)+n);
    }
    
    int minPathSum(vector<vector<int> > &grid) {
        int m = grid.size();
        int n = grid.at(0).size();
        int** dp = new int*[m];
        for(int i=0; i<m; i++) {
            dp[i] = new int[n];
        }
        
        return sub(grid, dp, m-1, n-1);
    }
};

Does anyone know why?

Thanks in advance.

How do you initialize the vector? Provide a SSCCE, that we can see all the relevant code. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jan 13, 2014 at 18:39
Your code has two new statements and no delete. All pointers to allocated memory in minPathSum are lost at return. This is a memory leak. (Though likely unrelated to your problem) — user3072164
– user3072164, Commented Jan 13, 2014 at 18:42
Also based on the top answers here and here you use dp[...][...] uninitialized and thus with indeterminate values. — user3072164
– user3072164, Commented Jan 13, 2014 at 18:57
if dp[...][...] is uninitialized, shouldn't all its elements be 0? @Nabla — UnkDrew
– UnkDrew, Commented Jan 13, 2014 at 19:24

user3072164 · Accepted Answer · 2014-01-14 19:29:19Z

0

My suggestions from the comments:

for(int i=0; i<m; i++) {
    dp[i] = new int[n];
}

return sub(grid, dp, m-1, n-1);

Here dp[i] is not zero-initialized, the values of dp[i] are indeterminate as dp is passed to sub. In sub the values are read before they are assigned to, so the behaviour may be very unexpected, in particular sub will return a indeterminate value from dp without doing anything else, if dp[m][n] is not zero, because of this test:

 if(dp[m][n] == 0) {

You might have been just lucky that the code ran correctly with your compiler. To correctly zero-initialize the values at declaration, use this:

 dp[i] = new int[n]();

answered Jan 14, 2014 at 19:29

user3072164

Sign up to request clarification or add additional context in comments.

Comments

UnkDrew · Accepted Answer · 2014-01-14 18:10:54Z

0

Nabla is right, replacing dp[i] = new int[n]; with dp[i] = new int[n](); does solve the problem.

answered Jan 14, 2014 at 18:10

UnkDrew

211 silver badge8 bronze badges

Collectives™ on Stack Overflow

Unexpected result from LeetCode (Minimum Path Sum)

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related