3

所以，基本上我感觉非常愚蠢，因为这个练习，我花了大约 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

其中矩阵参数是一个数组数组，每个数组代表三角形中的一行。

4

3 回答 3

6

如果您从底部开始并逐步向上，则此问题很容易。考虑三角形

   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 从他们那里偷走了它，显然没有注明出处，这真的不是一件好事。

于 2012-05-22T04:04:35.720 回答
1

注意：原始帖子中的问题陈述假设一个严格的直角三角形：

on each path the next number is located on the row below,
more precisely either directly below or below and one place to the right.

另请查看他们提供的示例以确认这一点。

回答：

  • 1]使用二维数组来存储三角形

  • 根据规则重新计算三角形

  • 走三角形的最后一行——即底边——找到最大值。

代码：

import java.util.Arrays;

public class NumberTriangle {

    //MAIN IS FOR TESTING ONLY
public static void main(String[] ars) {
    int[][] input = { { 1 }, { 4, 8 }, { 9, 8, 7 }, { 1, 3, 6, 9 },
            { 7, 5, 2, 7, 3 } };

    int max = compute(input);// answer: max length
    // not necessary; but shows new triangle
    for (int[] A : input)
        System.out.println(Arrays.toString(A));

    // print the answer
    System.out.println("Largest number: " + max);
}

    //THIS IS THE SOLUTION
public static int compute(int[][] input) {
    //compute new triangle
    for (int y = 1; y < input.length; y++)
        for (int x = 0; x < input[y].length; x++) {
            int first = x - 1 > 0 ? x - 1 : 0;
            int last = x < input[y - 1].length ? x
                    : input[y - 1].length - 1;
            int max = Math.max(input[y - 1][last], input[y - 1][first]);
            input[y][x] += max;
        }
    //extract max value;
    int max = -1;
    int lastRow = input[input.length - 1].length;
    for (int x = 0, y = input.length - 1; x < lastRow; x++)
        if (max < input[y][x])
            max = input[y][x];
    return max;
}// compute
}

测试用例答案：

[1]
[5, 9]
[14, 17, 16]
[15, 20, 23, 25]
[22, 25, 25, 32, 28]

Largest number: 32
于 2012-05-22T03:08:02.800 回答
0

最长路径查找方法对我来说感觉是错误的方法，因为每条路径都会有 N-1 条边长。我想我会通过假装输入是二叉树并找到树中最大的元素来开始该方法 - 找到底部两行的最大总和，在倒数第二行中记住结果，然后向上移动另一个排。（我希望这有某种意义......）

于 2012-05-22T01:29:34.457 回答