民路徑總和

Question

我工作的以下問題：

鑑於amxn網格填充非負數，發現從左上角到右下角的路徑，其合計最小所有的數字沿着它的路徑。 注意：您只能在任何時間點向下或向右移動。

這裏我最初的印象是，從網格中的每個位置得到最小長度的右邊和下邊。然而，這給了我以下不正確的答案：

Input: 
[[1,2],[1,1]] 
Output: 
2 
Expected: 
3 

直覺，不知道我在做什麼錯。這也是非常簡單的代碼（我知道它不是記事本 - 正在計劃下一步），但直覺上不知道發生了什麼問題。遞歸基本情況是有意義的，並且每個數字都被考慮在內。

def min_path_sum(grid) 
    smallest_path(0, 0, grid) 
end 

def smallest_path(row, col, grid) 
    return 0 if (row == grid.length || col == grid.first.length) 
    current_val = grid[row][col] 
    [current_val + smallest_path(row+1, col, grid), current_val + smallest_path(row, col+1, grid)].min #memoize here 

end 

Answer 1

您沒有做出正確的終止條件。你只檢查，直到你點擊的右列或最下一行。你需要保持在界限內，但是一直持續到你點擊右下角。您需要在範圍內重複出現，直到您點擊兩個的限制。

鑑於此，您的代碼確實工作正常：它找到2到底部行的路徑，而不是3到右側邊的路徑。你只需要教它完成這項工作。

這足以將您轉移到解決方案嗎？

Answer 2

由於這是無環有向圖上的最短路徑問題，因此可以使用標準shortest path algorithm。

您也可以使用動態規劃（「DP），這可能是最有效的優化技術。我的回答實現了DP算法。

最短路徑或DP算法將大大優於列舉所有路徑由於路徑數量隨着陣列大小呈指數增長，所以簡單的枚舉只能用於中等大小的陣列。

DP算法的思想如下：讓n和m分別是行數和列數，首先計算從最後一行中的每列到最後一列中的最短路徑最後一行。這是一個簡單的計算方法，因爲每個元素只有一條路徑爲[m-1, n-1]。從[m-1, n-2]開始，我們只需回到[m-1, 0]即可。

接下來我們計算從倒數第二行（m-2）開始並回到第一行（0）開始的每個其他行中每個元素到[m-1, n-1]的最短路徑。每行中的最後一個元素[i, n-1]是一個簡單的計算，因爲只能往下（至[i+1, n-1]）。因此，從[i, n-1]到[m-1, n-1]的最短路徑首先是[i+1, n-1]，然後是從[i+1, n-1]開始的最短路徑，這是我們已經計算出來的（當然包括它的長度）。從[i, n-1]開始的最短路徑的長度是[i, n-1]的「向下」距離加上從[i+1, n-1]開始的最短路徑的長度。

對於元素[i, j]，N-1 ,我< j < m-1，我們計算的最短路徑，如果我們走向右和向下，並選擇兩個短。

我們可以如下實現它。

代碼

def shortest_path(distance) 
    last_row, last_col = distance.size-1, distance.first.size-1 
    h = {} 
    last_row.downto(0) do |i| 
    last_col.downto(0) do |j| 
     h_right = { min_path_len: distance[i][j][:r] + h[[i,j+1]][:min_path_len], 
        next_node: [i,j+1] } if j < last_col 
     h_down = { min_path_len: distance[i][j][:d] + h[[i+1,j]][:min_path_len], 
        next_node: [i+1,j] } if i < last_row 
     g = 
     case 
     when i == last_row && j == last_col 
     { min_path_len: 0, next_node: nil } 
     when i == last_row 
     h_right 
     when j == last_col 
     h_down 
     else 
     [h_right, h_down].min_by { |f| f[:min_path_len] } 
     end 
     h[[i,j]] = g 
    end 
    end 
    build_path(h) 
end 

def build_path(h) 
    node = [0, 0] 
    len = h[node][:min_path_len] 
    arr = [] 
    while h[node][:next_node] 
    arr << node 
    node = h[node][:next_node] 
    end 
    [len, arr] 
end 

例

假設這些是相鄰節點之間的距離。

● 4 ● 3 ● 1 ● 2 ● 
6 2 5 4 5 
● 3 ● 4 ● 6 ● 3 ● 
1 3 4 2 3 
● 6 ● 3 ● 1 ● 2 ● 

以散列數組的形式提供這些信息很方便。

distance = [ 
    [{ r: 4, d: 6 }, { r: 3, d: 2 }, { r: 1, d: 5 }, { r: 2, d: 4 }, { d: 5 }], 
    [{ r: 3, d: 1 }, { r: 4, d: 3 }, { r: 6, d: 4 }, { r: 3, d: 2 }, { d: 3 }], 
    [{ r: 6 },  { r: 3 },  { r: 1 },  { r: 2 }] 
] 

我們現在可以計算最短路徑。

p shortest_path distance 
    #=> [15, [[0, 0], [0, 1], [1, 1], [2, 1], [2, 2], [2, 3]]] 

最短路徑由返回的數組的第二個元素給出。 15是該路徑的長度。