Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ayuda del ejercicio 4 del tema 5.3

Sea máximoValorRobable(i) el máximo valor que el ladrón puede obtener con las casas que hay desde la 0 hasta la i, ambas inclusive. El resultado que nos piden es máximoValorRobable(n - 1), siendo n la cantidad de casas.

Para obtener máximoValorRobable(i) el ladrón tiene que decidir si roba o no la casa i y elegir la mejor de las dos opciones:

Escribe las ecuaciones recursivas para calcular máximoValorRobable(i) siguiendo ese razonamiento, y después comprueba el resultado pulsando el enlace "Más ayuda".

Más ayuda

Si i > 1, máximoValorRobable(i) = max(valoresCasas[i] + máximoValorRobable(i - 2),
                                      máximoValorRobable(i - 1))

Si i = 1, máximoValorRobable(i) = max(valoresCasas[i],
                                      máximoValorRobable(i - 1))

                                = max(valoresCasas[1],
                                      valoresCasas[0])

Si i = 0, máximoValorRobable(i) = valoresCasas[0]
        

Por ejemplo, con valoresCasas = {6000, 10000, 3000, 15000, 4000, 2000, 8000, 5000}:

máximoValorRobable(7) = max(5000 + máximoValorRobable(5), // Robar la casa 7
                            máximoValorRobable(6))        // No robar la casa 7

máximoValorRobable(6) = max(8000 + máximoValorRobable(4), // Robar la casa 6
                            máximoValorRobable(5))        // No robar la casa 6

máximoValorRobable(5) = max(2000 + máximoValorRobable(3), // Robar la casa 5
                            máximoValorRobable(4))        // No robar la casa 5

...

máximoValorRobable(1) = max(10000,                        // Robar la casa 1
                            máximoValorRobable(0))        // No robar la casa 1

máximoValorRobable(0) = 6000                              // Robar la casa 0