DP novice's DP Solution (Java)


  • 0

    This is my first DP algorithm practice and I think DP is a real awsome idea and amazing, although it is not optimized it is accepted anyway.

    public class Solution198HouseRobber {
    
    	public int rob(int[] nums) {
    		if (nums.length == 0)
    			return 0;
    		int[] cacheProfit = new int[nums.length];
    		Arrays.fill(cacheProfit, -1);
    		return maxProfitToIndex(nums, cacheProfit, nums.length - 1);
    	}
    
    	/**
    	 * This method returns the max profit if I rob the first index houses
    	 * (nums[0...index]).
    	 */
    	private int maxProfitToIndex(int[] nums, int[] cache, int index) {
    		if (index == 0) {
    			cache[index] = nums[0];
    			return cache[0];
    		}
    		if (index == 1) {
    			cache[index] = Math.max(nums[0], nums[1]);
    			return cache[1];
    		}
    		if (cache[index] < 0)
    			cache[index] = Math.max(nums[index] + maxProfitToIndex(nums, cache, index - 2),
    					maxProfitToIndex(nums, cache, index - 1));
    		return cache[index];
    	}
    }
    

Log in to reply
 

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