Algoritmos y Estructuras de Datos (VJ1215)

Si a > 1, hasta la aldea a se puede llegar desde la aldea a - 1 con un paseo corto o desde la aldea a - 2 con un paseo largo. Hemos de elegir la mejor de las dos opciones, y para ello necesitamos saber cuál es el mínimo coste de llegar desde la primera aldea hasta cada una de esas dos aldeas. Eso lo podemos calcular recursivamente.

Para cualquier aldea a, sea mínimoCoste(a) el coste mínimo para llegar desde la aldea 0 hasta la aldea a. El resultado que nos piden es mínimoCoste(n - 1).

Si a = 0,
   mínimoCoste(a) = 0

Si a = 1,
   mínimoCoste(a) = mínimoCoste(a - 1) + paseoCorto[a - 1]
                  = paseoCorto[a - 1]

Si a > 1,
   mínimoCoste(a) = min(mínimoCoste(a - 1) + paseoCorto[a - 1],
                        mínimoCoste(a - 2) + paseoLargo[a - 2])
	

En ese cálculo recursivo hay cálculos que se repiten, y de ahí el interés de añadir una tabla para guardar mínimoCoste(a).

Sea u = n - 1 la última aldea.

Si a < u - 1, desde la aldea a podemos ir hasta la aldea a + 1 con un paseo corto o hasta la aldea a + 2 con un paseo largo. Hemos de elegir la mejor de las dos opciones, y para ello necesitamos saber cuál es el mínimo coste de llegar desde cada una de esas dos aldeas hasta la meta u. Eso lo podemos calcular recursivamente.

Para cualquier aldea a, sea mínimoCoste(a) el coste mínimo para llegar desde la aldea a hasta la aldea u. El resultado que nos piden es mínimoCoste(0).

Si a = u,
   mínimoCoste(a) = 0

Si a = u - 1,
   mínimoCoste(a) = mínimoCoste(a + 1) + paseoCorto[a]
                  = paseoCorto[a]

Si a < u - 1,
   mínimoCoste(a) = min(mínimoCoste(a + 1) + paseoCorto[a],
                        mínimoCoste(a + 2) + paseoLargo[a])
	

En ese cálculo recursivo hay cálculos que se repiten, y de ahí el interés de añadir una tabla para guardar mínimoCoste(a).