java - 三角拼图 : Find maximum total from top to bottom, 从顶部开始移动到相邻数字

Question

如标题所示，我需要解决这个难题。

       5
      9 6
     4 6 8 
    0 7 1 5

我需要找到的路径是从上到下的最大和，只移动到相邻的 child 。所以这条路径将是 5-9-6-7，总和为 27。

我的代码适用于我自己输入的每组数据，但是当我尝试使用提供的文本文件数据进行拼图时，我的总和/答案不被接受为正确的。

我这辈子都弄不明白我的代码有什么问题。有什么我没有看到的异常(exception)吗？

public class Triangle
{
    public static void main(String[] args) throws IOException
    {
        File file = new File("Tri.txt");
        byte[] bytes = new byte[(int) file.length()];
        try{
            //Read the file and add all integers into an array with the correct size. Array size is found with number of bytes file.length()
            //Parse string to integer
            FileInputStream fis = new FileInputStream(file);
            fis.read(bytes);
            fis.close();
            String[] valueStr = new String(bytes).trim().split("\\s+");
            int[] list = new int[valueStr.length];
            for (int i = 0; i < valueStr.length; i++) 
                list[i] = Integer.parseInt(valueStr[i]);

            System.out.println(computeMaxPath(list));
        }
        catch(Exception e)
        {
            e.printStackTrace();
        }
    }

    static int computeMaxPath(int[] list){

        //Disregard row number one since it is the root. Start row number count at 2
        int rowNumber = 2;
        //set the sum to the value of the root.
        int sum = list[0];
        //selected index begins at the root, index 0
        int selectedIndex = 0;

        for (int j = 1; j < list.length; j=j+rowNumber)
        {
            // for every iteration the right child is found by adding the current selected index by z. What is z?
            // the left child is of course found in the index -1 of the right child. 
            // z is the amount of of elements in the triangle's row. Row 3 has 3 elements, 4 has 4, etc. 
            // For exmaple, if the selectedIndex is index 4, its right child can be found by adding the index to the next row element count. 
            // 4 + 4 = 8 the right child is in index 8 and left is in index 7
            int rightChildIndex = selectedIndex + rowNumber;
            int leftChildIndex = selectedIndex + rowNumber - 1;

            //set the appropriate index for the greater child's index
            selectedIndex = list[rightChildIndex] >= list[leftChildIndex] ? rightChildIndex : leftChildIndex;

            //increment the sum of the path
            sum = sum + list[selectedIndex];

            System.out.println(selectedIndex);

            //increment the row number
            rowNumber++;
        }

        return sum;
    }
}

基本上，我的算法通过将文本文件中的整数字符串添加到数组中来工作。第一个选择的索引当然是根节点。为了找到正确的子索引，我将所选索引添加到下一行的长度，然后减去 1 以找到左子索引。

有什么想法吗？

Answer 1

这个算法使用了错误的逻辑。在这种情况下，您的算法可以工作，因为它具有使您的算法工作所需的属性，对于其他输入，情况显然并非如此。例如考虑以下(极端)示例:

          1
         1 0
        0 0 9

您的算法的工作原理是始终选择总和较大的 child ，因此在这种情况下，您的算法将生成路径 {1 , 1 , 0}，而正确的算法将生成{1、0、9}。

正确的算法需要遍历树并搜索所有路径才能找到正确的解决方案:

int findSum(int[] tree , int at_node){
    if(at_node >= length(tree))
        return 0 //end of the tree, quit recursive search

    //maximum-path including node is the path with the greatest sum that includes either the left or right child of the node.
    return max(findSum(tree , leftChild(at_node)) , 
                  findSum(tree , rightChild(at_node)) + tree[at_node]
}

---

正如@JohnBollinger 提到的:
这种从上到下的方法非常简单。但是效率成本。一种更有效但也更有效的解决方案，它只遍历每个节点一次。在上述算法中，表示访问每个节点的时间的树看起来像帕斯卡三角形，从而生成 2 ^ height 数组查找。自下而上的方法只需要 height + height - 1 + ... + 1 查找。

int findSumBottomTop(int[] tree , int height){
    //initialize counter for previous level
    int[] sums = new int[height + 1]
    fill(sums , 0)

    //counter for the level counts down to 1 (note that this variable is not 0-based!!!)
    int lvl = height

    //counter for nodes remaining on the current level (0-based)
    int remaining_in_lvl = lvl - 1
    //maximum-paths for each node on the current level
    int[] next_level = new int[lvl]

    //iterate over all nodes of the tree
    for(int node = length(tree) - 1; node > -1 ; node--){
        int left_max_path = sums[remaining_in_lvl]
        int right_max_path = sums[remaining_in_lvl + 1]

        next_level[remaining_in_lvl] = max(right_max_path , left_max_path) + tree[node]

        //decrement counter for remaining nodes
        remaining_in_lvl -= 1

        if(remaining_in_lvl == -1){
            //end of a level was encountered --> continue with lvl = lvl - 1
            lvl--
            //update to match length of next 
            remaining_in_lvl = lvl - 1

            //setup maximum-path counters for next level
            sums = next_level
            next_level = new int[sums.length - 1]
     }

     //there is exactly one sum remaining, which is the sum of the maximum-path
     return sums[0];
 }

基本思路如下:

 Consider this example tree:
     0    ^         6
    0 1   |        3 6
   0 1 2  |       1 3 5
  0 1 2 3 |      0 1 2 3
                0 0 0 0 0
tree   traversal  sums

sums 将是为每个级别生成的总和值。我们简单地从底部开始搜索，并搜索从一个级别中的每个节点到底部的最大路径。这将是左 child 的最大路径和右 child 的最大路径的最大值 + 节点的值。