我就是这样做的。
代码
def longest_path(arr)
return nil if arr.empty?
h = { len: arr.first.first, path: [] }
return h if arr.size == 1
arr[1..-1].reduce([h]) do |l,row|
h = l.first
left = { len: h[:len]+row.first, path: h[:path]+[:l] }
mid = l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
if h1[:len] >= h2[:len]
{ len: h1[:len]+v, path: h1[:path]+[:r] }
else
{ len: h2[:len]+v, path: h2[:path]+[:l] }
end
end
h = l.last
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
[left, *mid, right]
end.max_by { |h| h[:len] }
end
例子
a = [ [3],
[7,4],
[2,4,6],
[8,5,9,3]]
longest_path a
#=> {:len=>23, :path=>[:l, :r, :r]}
因此，最长路径的长度为 23。从3第一行向下和向左 ( :l) 到7第二行，向下和向右 ( :r) 到4第三行，向下和向右到9最后一行：3+7+4+9 => 23。
解释
这个问题与算法的选择同样重要。在我看来，后者相当明显：求解一排，用它求解两排，依此类推。
考虑上面的示例数组a。
arr = a
arr.empty? #=> false, so continue
h = { len: arr.first.first, path: [] }
#=> {:len=>3, :path=>[]}
return h if arr.size == 1 # arr.size => 4, so continue
作为
arr[1..-1] => [[7, 4], [2, 4, 6], [8, 5, 9, 3]]
reduce传递[h]并[7, 4]进入块并分配块变量：
l = [{ len: arr.first.first, path: [] }]
row = [7, 4]
然后计算：
h = l.first
#=> {:len=>3, :path=>[]}
left = { len: h[:len]+row.first, path: h[:path]+[:l] }
#=> {:len=>10, :path=>[:l]}
mid = []
h = l.last
#=> {:len=>3, :path=>[]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
#=> {:len=>7, :path=>[:r]}
[left, *mid, right]
#=> [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]
mid => []因为each_cons(2)在大小为 1 的数组上执行。
上面的最后一行提供了到第二行中两个元素中每一个元素的最长路径的信息。对于第一个元素 ( 7)，路径是有长度10的，从第一行中的唯一元素 ( 3) 开始，然后向下和“左” ( :l) 到给定元素。
正如在块[left, *mid, right]的最后一行中计算的那样reduce，块变量l被赋予该值以处理下一行arr：
l = [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]
row = [2, 4, 6]
接下来我们计算以下内容：
left = { len: h[:len]+row.first, path: h[:path]+[:l] }
#=> {:len=>5, :path=>[:l]}
l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
if h1[:len] >= h2[:len]
{ len: h1[:len]+v, path: h1[:path]+[:r] }
else
{ len: h2[:len]+v, path: h2[:path]+[:l] }
end
end
#=> [{:len=>14, :path=>[:l, :r]}]
h = l.last
#=> {:len=>7, :path=>[:r]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
#=> {:len=>13, :path=>[:r, :r]}
[left, *mid, right]
#=> [{:len=>5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
# {:len=>13, :path=>[:r, :r]}]
left和的计算right类似于对 的前一个元素所做的计算arr。我们来看看计算mid：
pairs = l.each_cons(2).to_a
#=> [[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]]
vals = pairs.zip(row[1..-2])
#=> pairs.zip([4])
#=> [[[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}], 4]]
vals是一个包含一个元素的数组。该元素被传递到map，分解并分配给块变量：
h1 = {:len=>10, :path=>[:l]}
h2 = {:len=> 7, :path=>[:r]}
v = 4
h1[:len] #=> 10
h2[:len] #=> 7
作为10 > 7，我们执行：
{ len: h1[:len]+v, path: h1[:path]+[:r] }
这是 的值mid。l现在为块值reduce分配了以下结果[left, *mid, right]：
l = [{:len=> 5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
{:len=>13, :path=>[:r, :r]}]
并开始处理第三行。reduce返回：
d = [{:len=>20, :path=>[:l, :l, :l]}, {:len=>19, :path=>[:l, :r, :l]},
{:len=>23, :path=>[:l, :r, :r]}, {:len=>16, :path=>[:r, :r, :r]}]
它提供了描述最后一行每个元素的最长路径的信息。最后一步是：
d.max_by { |h| h[:len] }
#=> {:len=>23, :path=>[:l, :r, :r]}