198. House Robber I/II

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 and it 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.

思路:
复杂度: Time O(n), Space O(n)

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] money = new int[nums.length + 1];
        money[0] = 0; // 第0次抢了0
        money[1] = nums[0]; // 第一次抢的nums[0]
        for (int i = 2; i < nums.length + 1; i++) {
            money[i] = Math.max(money[i - 1], money[i - 2] + nums[i - 1]);
        }
        return money[nums.length];
    }
}

房子成环。
思路: 抢第一个就不能抢最后一个,不抢第一个抢不抢最后一个随意
两种情况:
1.抢第一间(第二间必须不抢,第三间随意),不抢最后一间(倒数第二间随意)
2.不抢第一间(第二间随意),最后一间抢不抢随意(倒数第二间也随意)

public class Solution {
    // 1 2 4 6 4
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int n = nums.length;
        int[] robFirst = new int[n+1];
        int[] notRobFirst = new int[n+1];
        // init 
        robFirst[1] = nums[0];
        robFirst[2] = robFirst[1];
        notRobFirst[1] = 0;
        notRobFirst[2] = nums[1];

        for (int i = 3; i <= n - 1; i++) { // 第三次抢到n-1次
            robFirst[i] = Math.max(nums[i - 1] + robFirst[i - 2], robFirst[i - 1]);
        }
        for (int i = 3; i <= n; i++) { // 第三次抢到第n次
            notRobFirst[i] = Math.max(nums[i - 1] + notRobFirst[i - 2], notRobFirst[i-1]);
        }

        return Math.max(robFirst[n - 1], notRobFirst[n]);

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s