LeetCode - 198 House Robber

Difficulty：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 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.

思路

使用动态规划算出i个房子（nums.length=i）时的最大和（元素不能相邻）。

由于元素不能相邻，可以有这样两种相邻“抢劫”的方式：

1. 两个元素间隔一个元素
2. 两个元素间隔两个元素

代码

首先用一个比较直白的方法。
假设第i个元素为nums[i], 前i-3个元素的最大和sum1，前i-2个元素的最大和sum2，前i-1个元素的最大和sum3，则前i个元素的最大和sum有以下几个option：

1. 若选中该元素，依据不能相邻原则:

   sum = sum2 + nums[i] OR sum = sum1 + nums[i];

2. nums[i]没有被选中，则sum = sum3;

因此前i个元素的最大和sum = max(sum1 + nums[i], sum2 + nums[i], sum3);

• 上手版

这个代码不是很neat。

public class Solution {
    public int rob(int[] nums) {
        int sum1 = 0;
        int sum2 = 0;
        int sum3 = 0;
        int sum = 0;
        if(nums==null || nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return max(nums[0], nums[1]);
        if(nums.length==3) return max(nums[0]+nums[2], nums[1]);
        sum1 = nums[0];
        sum2 = max(nums[0], nums[1]);
        sum3 = max(nums[0]+nums[2], nums[1]);
        for(int i=3; i<nums.length; i++) {
            sum = max(max(nums[i]+sum2, nums[i]+sum1),sum3);
            sum1 = sum2;
            sum2 = sum3;
            sum3 = sum;
        }
        return sum;
    }
    
    public int max(int a, int b) {
        return a>b?a:b;
    }
}

下面这个方法的思想是一样的，只不过用了很巧妙的方式极大缩短了代码。

• 进阶版

public class Solution {
    public int rob(int[] nums) {
        int a = 0;
        int b = 0;
    
        for (int i=0; i<nums.length; i++) {
            if (i%2==0) {
                a = max(a+nums[i], b);
            }
            else {
                b = max(a, b+nums[i]);
            }
        }
        return max(a, b);
    }
    
    public int max(int a, int b) {
        return a>b?a:b;
    }
}

原题链接：https://leetcode.com/problems/house-robber/

• ← Previous Post
• Next Post →