无法从CodeChef解决练习[简单]

Question

所以,基本上我感觉非常愚蠢,因为这个练习,我花了4到5个小时试图编码,到目前为止我还没有成功.

我已经意识到使用最长路径方法使用树遍历可以更容易地解决这个问题,但是我不确定(你能不能向我证实这一点.),可能是过度杀死因为它应该是这是一个容易出问题的问题,那么请您帮我解决一下如何解决这个问题的一些指导或基本步骤或算法方法？各种帮助当然值得赞赏.

PS.我通常会发布一些关于我到目前为止所做的事情的代码,但我相信到目前为止,一切都是错误的,我宁愿从头开始,至少在想法方面.

谢谢.

根据请求,这里是根据解决练习的接受答案键入的代码:

def get_max_sum(matrix)
  (1...matrix.length).each do |index|  
    flag = 0  
    matrix[index].each_with_index do |e, i|    
      add = (matrix[index-1][flag] > matrix[index-1][flag+1]) ? matrix[index-1][flag] : matrix[index-1][flag+1]
      e += add
      matrix[index][i] = e
      flag = flag + 1
    end    
  end
  matrix[-1][0]
end

矩阵参数是一个数组数组,每个数组代表一个三角形的行.

Answer 1

如果从底部开始并逐步完成,这个问题很容易.考虑三角形

   1
  1 2
 4 1 2
2 3 1 1

看看倒数第二行.如果通过三角形的某个路径到达4,你将向右移动到3,得到7的总和(加上它上面的路径中的任何东西).如果你已经达到1,你将向左移动到3,得到4的总和(加上它上面的路径中的任何东西).如果你在2,你可以移动任何一种方式获得3的总和(加上它上面的路径中的任何东西).因此,通过用和来替换倒数第二行,即三角形

  1
 1 2
7 4 3

将具有与原始三角形相同的最大和路径.现在以递减三角形递归地执行相同的过程.从倒数第二行的1开始向左移动到7,得到8的总和,从2向左移动到4,得到6的总和.减少的三角形现在看起来像

 1
8 6

最后,从倒数第二行的1开始向左移动到8,总和为9,这就是问题的答案.

还有一种从上到下工作的方法.在每一步中,将三角形中的每个数字替换为通向该数字的任何路径的最大总和.从顶部开始,三角形开始

1

然后第二行被其总和替换

 1
2 3

然后是第三排

  1
 2 3
6 4 5

最后是第四排

   1
  2 3
 6 4 5
8 9 6 6

答案是底行中最大的总和,即9.我总是发现自上而下的方法比自下而上的方法更难管理,但这两种算法是相互对立的,所以你选择哪个实施.自上而下的方法确实具有以下优势:您可以在读取数据时累积下一行; 使用自下而上的方法,您必须在计算任何总和之前读取并存储整个输入.

我会留给你写代码.执行此操作时,请记住,您一次只需要存储两行,即前一行和下一行.哪个是上一个,哪个是下一个取决于您是自上而下还是自下而上 - 前一行是您刚刚填写的行,下一行是您当前正在处理的行,这意味着如果你的工作自上而下的下一行有一个比以前更加一行总和,如果你的工作自下而上的下一行有一个比以前少排总和.请在工作时发布您的代码,以便其他人可以从您的努力中学习.

顺便说一下,这个问题最初来自Project Euler.Code Chef偷了它们,显然没有归属,这真的不是一件好事.