[LeetCode] 0198. Ladrón de casas

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Medio

Eres un ladrón profesional que planea robar casas a lo largo de una calle. Cada casa tiene una cierta cantidad de dinero escondida, la única limitación que te impide robar en cada una de ellas es que las casas adyacentes tengan sistemas de seguridad conectados y. Se pondrá en contacto automáticamente con la policía si dos casas adyacentes fueron asaltadas la misma noche..

Dada una matriz de enteros números representando la cantidad de dinero de cada casa, devolver la cantidad máxima de dinero que puedes robar esta noche sin alertar a la policía.

Ejemplo 1:

Aporte: números = [1,2,3,1]
Producción: 4
Explicación: Roba la casa 1 (dinero = 1) y luego roba la casa 3 (dinero = 3). Cantidad total que puedes robar = 1 + 3 = 4.

Ejemplo 2:

Aporte: números = [2,7,9,3,1]
Producción: 12
Explicación: Roba la casa 1 (dinero = 2), roba la casa 3 (dinero = 9) y roba la casa 5 (dinero = 1). Cantidad total que puedes robar = 2 + 9 + 1 = 12.

Restricciones:

1 <= números.longitud <= 100
0 <= números[i] <= 400

Tabla de contenido

Pitón

				
					Complejidad de tiempo de #: O(n) Complejidad de espacio de #: O(1) al escribir import List class Solución: def __init__(self) -> Ninguno: self.memo = {} def rob(self, nums: List[int]) -> int: self.memo = {} return self.robFrom(0, nums) def robFrom(self, i, nums): si i >= len(nums): devuelve 0 si estoy en self.memo: devuelve self. memo[i] self.memo[i] = max(self.robFrom(i+1, nums), self.robFrom(i+2, nums) + nums[i]) return self.memo[i] nums = [ 1, 2, 3, 1] imprimir(Solución().rob(numeros))

Pitón

Artículos relacionados