民路径总和

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是该路径的长度。