Java Memoization Solution


  • 0
    P
    public class Solution {
        Map<Integer, Integer> memoStartFirst = new HashMap<Integer, Integer>();
        Map<Integer, Integer> memoStartSecond = new HashMap<Integer, Integer>();
        
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            return max(robStartFirst(nums, nums.length - 1), robStartSecond(nums, nums.length - 1));
        }
        
        private int robStartFirst(int[] nums, int n){
            if (memoStartFirst.containsKey(n)) return memoStartFirst.get(n);
            
            int k;
            if (n < 0) return 0;
            else if (n == 0) k = nums[0];
            else{
                if (n == nums.length - 1) {
                    k = robStartFirst(nums, n-1);   // exclude last house since we chose first house
                } else {
                    k = max(robStartFirst(nums, n-2) + nums[n], robStartFirst(nums, n-3) + nums[n - 1]);
                }
            }
            memoStartFirst.put(n,k);
            return k;
        }
        
        private int robStartSecond(int[] nums, int n){
            if (memoStartSecond.containsKey(n)) return memoStartSecond.get(n);
            
            int k;
            if (n <= 0) k = 0; //exclude first house
            else if (n == 1) k = nums[1]; 
            else{
                k = max(robStartSecond(nums, n-2) + nums[n], robStartSecond(nums, n-3) + nums[n - 1]);
            }
            memoStartSecond.put(n,k);
            return k;
        }
        
        private int max (int a, int b){
            if (a > b) return a;
            return b;
        }
    }

Log in to reply
 

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