198. House Robber (Easy)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution 1: DP O(n); O(n)

dp[i] means the the maximum amount of money you can rob from the first i houses.

    public int rob(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        if (n == 1) { //since we need to use nums[1] below, we should check nums' length first.
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); //two choices: rob, not rob
        }
        return dp[n - 1];
    }

Solution 2: DP O(n); O(1)

https://leetcode.com/problems/house-robber/solution/ 这种写法很好解释，变量对应关系很明确。

    public int rob(int[] nums) {
        int preMax = 0; //dp[i - 2]
        int curMax = 0; //dp[i - 1]
        for (int num : nums) {
            int temp = curMax;
            // dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); //two choices: rob, not rob
            curMax = Math.max(preMax + num, curMax); //dp[i - 1] -> dp[i]
            preMax = temp; //dp[i - 2] -> dp[i - 1]
        }
        return curMax;
    }

Solution 3: DP O(n); O(1)

     [1, 3, 2, 4, 1]
          No  Yes
     1 :  0    1
     3 :  1    3
     2 :  3    3

这种写法中的两个变量含义和上面的完全不一样，所以最后返回时还要取max。

    public int rob(int[] nums) {
        int prevNo = 0;
        int prevYes = 0;
        for (int num : nums) {
            int temp = prevNo;
            prevNo = Math.max(prevNo, prevYes);
            prevYes = num + temp;
        }
        return Math.max(prevNo, prevYes);
    }