198 House Robber

LeetCode

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

经典动态规划题。抢到当前房屋的收获最大值有 2 种情况，要么不抢当前的，此时最大值和抢到上一个房屋相同，要么上一个房屋不抢，此时最大值为抢到上上个房屋的最大值加上这个房屋的价值。时间复杂度 O(n)。有如下关系 dp[i] = max( nums[i]+dp[i-2] , dp[i-1] )

public int rob(int[] nums) {
    if(nums==null || nums.length==0) return 0;
    int pre1=0,pre2=0,max=0;
    for(int i:nums){
        max=Math.max(pre1+i,pre2);
        pre1=pre2;
        pre2=max;
    }
    return max;
}