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 restricción que le impide robar a cada una de ellas es que las casas adyacentes tienen un sistema de seguridad conectado y se comunicará automáticamente con la policía si dos casas adyacentes fueron asaltadas la misma noche.
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.
Solución Java 1 – Programación dinámica
La clave es encontrar la relación dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]).
public int rob(int[] nums) { if(nums==null||nums.length==0) return 0; if(nums.length==1) return nums[0]; int[] dp = new int[nums.length]; dp[0]=nums[0]; dp[1]=Math.max(nums[0], nums[1]); for(int i=2; i<nums.length; i++){ dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]); } return dp[nums.length-1]; } |
Solución Java 2
Podemos usar dos variables, pares e impares, para rastrear el valor máximo hasta el punto de iterar la matriz. Puede utilizar el siguiente ejemplo para recorrer el código.
50 1 1 50
public int rob(int[] num) { if(num==null || num.length == 0) return 0; int even = 0; int odd = 0; for (int i = 0; i < num.length; i++) { if (i % 2 == 0) { even += num[i]; even = even > odd ? even : odd; } else { odd += num[i]; odd = even > odd ? even : odd; } } return even > odd ? even : odd; } |
Solución Java 3: programación dinámica con memorización
public int rob(int[] nums) { if(nums.length==0){ return 0; } int[] mem = new int[nums.length+1]; Arrays.fill(mem, -1); mem[0] = 0; return helper(nums.length, mem, nums); } private int helper(int size, int[] mem, int[] nums){ if(size <1){ return 0; } if(mem[size]!=-1){ return mem[size]; } //two cases int firstSelected = helper(size-2, mem, nums) + nums[nums.length -size]; int firstUnselected = helper(size-1, mem, nums); return mem[size] = Math.max(firstSelected, firstUnselected); } |
