198. House Robber

四刷 06/2022

Version #1 DP with Constant Space

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber.

Memory Usage: 41.5 MB, less than 45.61% of Java online submissions for House Robber.

class Solution {

    public int rob(int[] nums) {

        // dp[i] - the max amount of money to rob the [0, i) houses

        // dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2])

        int prevprev = 0;

        // dp[0] = 0

        int prev = nums[0];

        for (int i = 2; i <= nums.length; i++) {

            int curr = Math.max(prev, prevprev + nums[i - 1]);

            prevprev = prev;

            prev = curr;

        }

        return prev;

    }

}

三刷
发现这个题有两种定义方法
1. dp[i] -> The max profit to rob the previous i house
2. dp[i][0] -> not rob house i
    dp[i][0] -> rob house i

Time O(n) Space O(1)
100.00 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
       
        int prevprev = 0;
        int prev = nums[0];
        int curr = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            curr = Math.max(nums[i - 1] + prevprev, prev);
            prevprev = prev;
            prev = curr;
        }
        return curr;
    }
}

56.85 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length + 1];
        // The max profit to rob the previous i house
        // dp[1] the max profit to either rob house 0 or not
        //
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length];
    }
}

二刷
DP定义不一样了， 也是一种思路
100.00 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 2 states
        int[][] dp = new int[nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // Not rob current house
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = nums[i] + dp[i - 1][0];
        }
        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}


Optimized Space
100.00 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 2 states
        int dpNotRobPrev = 0;
        int dpRobPrev = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // Not rob current house
            int dpNotRobCurr = Math.max(dpNotRobPrev, dpRobPrev);
            int dpRobCurr = nums[i] + dpNotRobPrev;
            dpNotRobPrev = dpNotRobCurr;
            dpRobPrev = dpRobCurr;
        }
        return Math.max(dpNotRobPrev, dpRobPrev);
    }
}


Version #1 DP O(n) space

一刷
public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length + 1];
        //dp[i] - the max profit to rob the previous ith houses
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length];
    }
}

Version #2 Rolling Array
O(1) Space
42.03 %

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //int[] dp = new int[nums.length + 1];
        //dp[i] - the max profit to rob the previous ith houses
        int prevPrev = 0;
        int prev = nums[0];
        int curr = prev; //If only 1 house
        for (int i = 2; i <= nums.length; i++) {
            curr = Math.max(nums[i - 1] + prevPrev, prev);
            prevPrev = prev;
            prev = curr;
        }
        return curr;
    }
}