LeetCode的意外結果（最小路徑總和）

-1

我使用了一個在線編譯器來測試我的代碼，並且它運行正常。但是，當我將代碼提交給LeetCode時，它總是返回一個隨機負數，如-1218055056。LeetCode的意外結果（最小路徑總和）

的問題描述如下，

給定一個m×n個柵格填充有非負數，找到從左上角到沿其路徑中的所有數字的總和最小化右下方的路徑。

注意：您只能在任何時間點向下或向右移動。

而且我的代碼如下，

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); 
    } 
};

有誰知道爲什麼嗎？

在此先感謝。

來源

2014-01-13 UnkDrew

如何初始化矢量？提供[SSCCE]（http://meta.stackexchange.com/questions/22754/sscce-how-to-provide-examples-for-programming-questions），我們可以看到所有相關的代碼。 –

你的代碼有兩個'new'語句，沒有'delete'。在'minPathSum'中分配內存的所有指針在返回時都會丟失。這是內存泄漏。（雖然可能與您的問題無關） – Nabla

哪一行輸出意外值？ –

我從意見建議：

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

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

這裏dp[i]是不零初始化的dp[i]值是不確定爲dp傳遞給sub。在sub讀值，他們被分配到前，所以其行爲可能是很意外的，特別是sub將從dp返回一個不確定的值，而不做別的事情，如果dp[m][n]不爲零，因爲這個測試：

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

你可能很幸運，代碼在你的編譯器中正確運行。要在聲明中正確初始化零值，請使用：

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

來源

2014-01-14 19:29:19 Nabla

Nabla是對的，用dp[i] = new int[n]();代替dp[i] = new int[n];確實解決了這個問題。

來源

2014-01-14 18:10:54 UnkDrew

LeetCode的意外結果（最小路徑總和）

回答

相關問題