Problema con el problema Project Euler 18

Question

Actualmente estoy tratando de resolver problem 18 of project Euler. El objetivo es:

Al comenzar en la parte superior del triángulo de abajo y moviéndose a números adyacentes en la fila de abajo, el volumen total máximo de arriba a abajo es 23.

 
     3 
    7 4 
    2 4 6 
    8 5 9 3 

Esto es, 3 + 7 + 4 + 9 = 23.

Encontrar el volumen total máximo de arriba a abajo del triángulo a continuación:

 
       75 
       95 64 
       17 47 82 
       18 35 87 10 
      20 04 82 47 65 
      19 01 23 75 03 34 
      88 02 77 73 07 63 67 
      99 65 04 28 06 16 70 92 
     41 41 26 56 83 40 80 70 33 
     41 48 72 33 47 32 37 16 94 29 
     53 71 44 65 25 43 91 52 97 51 14 
     70 11 33 28 77 73 17 78 39 68 17 57 
    91 71 52 38 17 14 91 43 58 50 27 29 48 
    63 66 04 68 89 53 67 30 73 16 69 87 40 31 
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 

Me trataron de resolverlo con el siguiente algoritmo:

public static void main(String[] args) throws NumberFormatException, IOException { 

     int[][] values = readFile(); 
     int depth = values.length - 2; 

     while (depth >= 0) { 
      for (int j = 0; j < depth; j++) { 
       values[depth][j] += Math.max(values[depth+1][j], values[depth+1][j+1]); 
      } 
      depth += -1; 
     } 

     values[0][0] += Math.max(values[1][0], values[1][1]); 

      System.out.println("The maximum path sum is: " + values[0][0]); 
    } 

Los valores de la matriz contiene todos los números desde el triángulo donde values[0][0] es el elemento en la fila superior y values[n][n] es el último elemento en la última fila.

El algoritmo usa el enfoque de que si, por ejemplo, comienzo en la última fila y tengo la opción entre 04 + 63 y 62 + 63, la suma del campo en el que 63 se fijará en 125 porque esta es mayor cantidad Este algoritmo funciona para el triángulo pequeño, pero para el triángulo grande parece fallar. No estoy seguro por qué y agradecería cada pista.

Answer 1

creo que la línea:

for (int j = 0; j < depth; j++) { 

debe ser

for (int j = 0; j <= depth; j++) { 

porque en este momento no esté visitando el último elemento de cada fila. Por supuesto, entonces no necesita la línea

values[0][0] += Math.max(values[1][0], values[1][1]); 

porque ya está hecha en el circuito.

Answer 2

Puede que esta no sea la mejor solución, pero ¿qué pasa si en cada iteración mantienes un registro de la suma hasta ese punto? Luego, cuando vayas a la última fila, el valor máximo sería tu respuesta.

Answer 3

No conozco el algoritmo correcto, pero hay una prueba fácil de que @Johns comenta sobre la pregunta, que la mejor opción local no conduce necesariamente a la mejor solución global.

consideran este (extremo) ejemplo:

 
    1 
    1 0 
    1 0 1000 
1 0 0 0 
1 0 0 0 0 

Dado su algoritmo, que obviamente había Baja por el extremo izquierdo del camino y nunca leen el 1000 que debe estar en el mejor camino.