En un pueblo, la gente construye casas en el mismo lado de la carretera. Un ladrón planea saquear el pueblo. Quiere la máxima cantidad de dinero sin tener ningún riesgo de ser atrapado. De alguna manera, los aldeanos saben que su casa adyacente está siendo saqueada o no y por lo tanto se ponen alerta. Así el ladrón no puede saquear dos casas contiguas. Dado que el ladrón sabe la cantidad de dinero que hay en cada casa y el camino es recto y no hay vuelta, ¿cuál es la estrategia algorítmica más eficiente para resolver este problema?
(A) Fuerza bruta
(B) Programación dinámica
(C) Retroceso
(D) Divide y vencerás
Respuesta: (B)
Explicación:
If we take a closer look, the problem boils down to: Given an array with some finite size where each element represents a positive number, find the maximum sum such that no two elements are adjacent. Dynamic Programming is the efficient technique to solve this. The algorithm can be given as follows: Maintain an auxiliary array loot. loot[0] = arr[0] loot[1] = arr[1] loot[i] = max(loot[i - 1], loot[i - 2] + arr[i]), 2 <= i < n loot[n - 1] gives the maximum amount of money the thief can take away.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA