LeetCode – Ladrón de casas II (Java)

Después de robar esas casas en esa calle, el ladrón se ha encontrado un nuevo lugar para su robo para que no reciba demasiada atención. Esta vez, todas las casas de este lugar están dispuestas en círculo. Eso significa que la primera casa es vecina de la última. Mientras tanto, el sistema de seguridad de estas casas sigue siendo el mismo que el de la calle anterior.

Dada una lista de números enteros no negativos que representan la cantidad de dinero de cada casa, determina la cantidad máxima de dinero que puedes robar esta noche sin alertar a la policía.

Análisis

Esta es una extensión de House Robber. Aquí hay dos casos 1) El primer elemento está incluido y el último no está incluido 2) El primero no está incluido y el último está incluido. Por lo tanto, podemos usar el enfoque de programación dinámica similar para escanear la matriz dos veces y obtener el valor mayor.

Solución Java

public int rob(int[] nums) {
    if(nums==null || nums.length==0)
        return 0; 
 
    if(nums.length==1)
        return nums[0];
 
    int max1 = robHelper(nums, 0, nums.length-2);
    int max2 = robHelper(nums, 1, nums.length-1);
 
    return Math.max(max1, max2);
}
 
public int robHelper(int[] nums, int i, int j){
    if(i==j){
        return nums[i];
    }
 
    int[] dp = new int[nums.length];
    dp[i]=nums[i];
    dp[i+1]=Math.max(nums[i+1], dp[i]);
 
    for(int k=i+2; k<=j; k++){
        dp[k]=Math.max(dp[k-1], dp[k-2]+nums[k]);    
    }
 
    return dp[j];
}