Максимальная длина пути

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

вы используете путь, который мог только заполните треугольник, который у вас есть. однако вы можете использовать более динамичный способ, как рекурсия, в основном это сверху вниз. он начинается с вершины треугольника и намного быстрее смотрит на самый высокий путь.

Но если вы хотите помочь с кодом конкретно идентификатор сказать, вы имели в виду, чтобы добавить один к вашей строке переменной

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); 

} 
}