Ac solution code


  • 1

    Special thanks to tusizi

    The basic idea is based on DP, while DFS method will take O(n!) runtime approximately.

    Solution1. DP - O(n) runtime; O(1) space

    public int rob(int[] nums) {
    	//prevNo : we don't rob the previous house
    	//prevYes: we rob the previous house
    	int prevYes = 0, prevNo = 0; 
    	for (int i : nums) { 
    	    int tmp = prevYes;
    		prevYes = prevNo + i;
    		prevNo = Math.max(tmp, prevNo);
    	}			
    	return Math.max(prevNo, prevYes);
    }
    

    Solution2. DP - O(n) runtime; O(n) space

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
    	int dp[][] = new int[nums.length][2];// dp[i][0]: we don't rob house i; dp[i][1]: we rob house i
    	dp[0][0] = 0;// Initialize house 0
    	dp[0][1] = nums[0]; 
    	
    	for (int i = 1; i < nums.length; i++) {
    		dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
    		dp[i][1] = dp[i-1][0] + nums[i];    		
    	}
    	return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);
    }
    

    Solution3. DFS - O(n!) runtime - TLE (Only for reference)

    DP is generally retrieved from DFS solution, while this DFS solution is the origin of DP idea. Gonna optimize this solution with memorization later.

    int max = 0;
    public int rob(int[] nums) {		
    	DFS(nums, new boolean[nums.length], 0, 0);
    	return max;
    }	
    void DFS(int[] nums, boolean[] visited, int start, int curSum) {
    	for (int i = start; i < nums.length; i++) {
    		if (!visited[i]) {
    			visited[i] = true;
    			max = Math.max(max, curSum + nums[i]);
    			DFS(nums, visited, i + 2, curSum + nums[i]);
    			visited[i] = false;				
    		}
    	}	
    } 
    

Log in to reply
 

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