Java O(n) DP solution with 13 lines clean code.


  • 18
    L
     public int rob(int[] num) {
    		int n = num.length;
    		if (n < 2)
    			return n == 0 ? 0 : num[0];
    		int[] cache = new int[n];
    		cache[0] = num[0];
    		cache[1] = num[0] > num[1] ? num[0] : num[1];
    		for (int i = 2; i < n; i++) {
    			cache[i] = cache[i - 2] + num[i];
    			cache[i] = cache[i] > cache[i-1]? cache[i] : cache[i-1];
    		}
    		return cache[n - 1];
    	}

  • 0
    N

    Could anyone explain why it works ?


  • 0
    R
    public int rob(int[] num) {
            if (num == null || num.length == 0) return 0;
            int size = num.length;
            if (size == 1) return num[0];
            int[] res = new int[size+1];
            res[size-1] = num[size-1];
            for (int i = size-2; i >= 0; --i)
                res[i] = max(num[i] + res[i+2], res[i+1]);
            return res[0];
        }

  • -1
    R

    It works because it is a basic dynamic programming solution. It is the same as my solution below written in a style you may be familiar with.


  • 0
    D

    0 houses return 0.

    1 house returns num[0].

    2 houses return whichever larger.

    For n houses where n>2:

    Consider the last house num[n-1]. It is either robbed, or NOT robbed.

    If robbed, then amount of money is (total of n-2 houses) + num[n-1].

    If NOT robbed, then amount of money is (total of n-1 houses).

    Return whichever larger.


  • 10
    D
    public class Solution {
        public int rob(int[] num) {
            int rob = 0, noRob = 0;
            for (int i = 0; i < num.length; i++) {
                int temp = noRob;
                noRob = Math.max(rob, noRob);
                rob = temp + num[i];
            }
            return Math.max(rob, noRob);
        }
    }

Log in to reply
 

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