最大路径总和

Question

我想开发一个Java程序来解决https://projecteuler.net/problem=18。不过我碰到的困难，我不知道为什么这个代码不工作：

int[][] testTriangle = { 
      {3}, 
      {7, 4}, 
      {2, 4, 6}, 
      {8, 5, 9, 3} 
    }; 

    HashMap<Integer, Integer> hasGoneDownRoute = new HashMap<Integer, Integer>(); //Stores numbers and start positions to numbers 

    int largestValue = 0; 
    int value = 0; 
    int row = testTriangle.length-1; 
    for (int startPosition = 0; startPosition <= testTriangle[row].length-1; startPosition++) { //starts from all possible start positions on the bottom row 
     for (int y = 1; y<=2; y++) { //executes from the same start position twice to get all possible routes (ACTUALLY THIS MIGHT BE WRONG!?) 
      while (row != 0) { //until it reaches the top row 
       if (startPosition == 0) { //if it's on the far left 
        value += testTriangle[row-1][0]; 
       } 
       else if (startPosition == testTriangle[row].length-1) { //if at's on the far right 
        value += testTriangle[row-1][testTriangle[row-1].length-1]; //set the value to the row above it on the far right 
       } 
       else { //This never gets called? 
        int noToChooseFrom1 = testTriangle[row-1][startPosition]; //above it and to the right 
        int noToChooseFrom2 = testTriangle[row-1][startPosition-1]; //above it and to the left 
        if (hasGoneDownRoute.containsKey(noToChooseFrom1) && hasGoneDownRoute.get(noToChooseFrom1) == startPosition) { //checks if it has gone down a certain route before 
         value += noToChooseFrom2; 
         hasGoneDownRoute.put(testTriangle[row-1][startPosition-1], startPosition); 
        } 
        else { 
         value += noToChooseFrom1; 
         hasGoneDownRoute.put(noToChooseFrom1, startPosition); 
        } 
       } 
       row--; 
      } 
     } 
     if (value > largestValue) { 
      largestValue = value; 
     } 
     System.out.println(largestValue); 
    } 

我刚添加笔记，试图解释我的思维过程

Answer 1

您使用的方式，只可能完成你所拥有的三角形。然而，你可以使用更像动态递归的方式，这基本上是自上而下的。它从三角形的顶部开始，并以更快的速度俯视最高路径。

但是如果你想与您的代码有助于明确ID说你的意思是添加一个到你的行变量

public class helping 
{ 

public static int rec(int [][] triangle) 
{ 
    return highestPath(triangle,0,0); 

} 

private static int highestPath(int[][] triangle, int row, int col) 
{ 
    if(row==triangle.length-1) 
    { 
     try // try catch is used instead of an if statement to see if the col is at the end 
     { 
     if(triangle[row][col]>triangle[row][col+1]) 
      return triangle[row][col]; 
     else 
      return triangle[row][col+1]; 
     } 
     catch(Exception e){return triangle[row][col];} 
    } 
    else 
    { 
     if(col!=triangle[row+1].length-1) 
     { 
      if(highestPath(triangle, row+1, col)>highestPath(triangle, row+1, col+1)) 
       return triangle[row][col]+highestPath(triangle, row+1, col); 
      else 
       return triangle[row][col]+highestPath(triangle, row+1, col+1); 
     } 
    } 
    return triangle[row][col]+highestPath(triangle, row+1, col); 
} 

public static void main(String args[])throws Exception 
{ 
    int[][] testTriangle = { 
      {3}, 
      {7, 4}, 
      {2, 4, 6}, 
      {8, 5, 9, 3} 

    }; 
    int max=rec(testTriangle); 

    System.out.println(max); 

} 
}