Java DP solution (Memoization) with explanation


  • -2
    P
    public class Solution {
        Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
        
        /**
         * return max amount of money that can be robbed from all house houses without triggering alarm
         * @param nums array of amount of money in each house
         * 
         * @return max amount of money that can be robbed from all houses without triggering alarm 
         **/
        public int rob(int[] nums) {
            if (nums == null) return 0;
            return rob_aux(nums, nums.length);
        }
        
        /**
         * return max amount of money robbed from first n houses
         * @param nums amount of money in each house
         * @param n number of house
         * 
         * @return max amount of money can be robbed from house [0-n) without triggering alarm 
         **/
        private int rob_aux(int[] nums, int n){
            if (memo.containsKey(n)) return memo.get(n);
            int k;
            
            if (n <= 0){
                //no house
                return 0;
            } else if (n == 1) {
                //house 0 only
                k = nums[0];
            } else {
                //M[n] = max amount of money can be robbed from house [0-n) without triggering alarm
                //L[n] = amount of money in house n
                //M[n] = MAX(M[n-1] + L[n], M[n-2] +  L[n-1])
                k = max(rob_aux(nums, n-2) + nums[n-1], rob_aux(nums, n-3) + nums[n-2]);
            }
            memo.put(n,k);
            return k;
        }
        
        private int max(int a, int b){
            if(a > b) return a;
            return b;
        }
    }

  • 0
    S

    M[n] = MAX(M[n-1] + L[n], M[n-2], L[n-1]) there is one obvious text typing error :)
    should be M[n] = MAX(M[n-1] + L[n], M[n-2] [+] L[n-1])


  • 0
    P

    you are right!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.