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](http://meta.stackexchange.com/questions/22754/sscce-how-to-provide-examples-for-programming-questions), that we can see all the relevant code. — πάντα ῥεῖ, Jan 13 '14 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) — , Jan 13 '14 at 18:42
Also based on the top answers [here](http://stackoverflow.com/questions/620137/do-the-parentheses-after-the-type-name-make-a-difference-with-new) and [here](http://stackoverflow.com/questions/1628311/array-initialisation) you use `dp[...][...]` uninitialized and thus with indeterminate values. — , Jan 13 '14 at 18:57
if `dp[...][...]` is uninitialized, shouldn't all its elements be 0? @Nabla — UnkDrew, Jan 13 '14 at 19:24
@UnkDrew No read the links I posted, they say `indeterminate`. — , Jan 13 '14 at 19:25
I set the vector to be [[1]], and it should return 1, but some random negative number instead @πάνταῥεῖ — UnkDrew, Jan 13 '14 at 19:25
@UnkDrew Replace `dp[i] = new int[n];` with `dp[i] = new int[n]();` and report your findings. I am not sure I am correct, but interested. — , Jan 13 '14 at 19:27
So if I initialize all its elements to 0, will it solve the problem? @Nabla is it what you want to do? — UnkDrew, Jan 13 '14 at 19:27
I'd guess your vectors need to be initialized (`resize()`) correctly for the correct grid dimensions. — πάντα ῥεῖ, Jan 13 '14 at 19:28

score 0 · Answer 1 · answered Jan 14 '14 at 18:10

0

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

answered Jan 14 '14 at 18:10

UnkDrew

21
1
8

score 0 · Accepted Answer · answered Jan 14 '14 at 19:29

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]();

Unexpected result from LeetCode (Minimum Path Sum)

2 Answers2