导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:O(n)
    2. 方法二:O(1)

LeetCode-198.House Robber

题目

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 .

翻译

你是一个职业小偷,计划去抢一条街上的房子。每栋房子藏着一定数量的钱,唯一能阻止你偷盗的限制是,相邻的房子有相连的安全系统,并且会在相邻的两栋房子在同一晚被侵入后自动报警。
给出一个非负整数的数组代表每个房子的钱数,计算出在不会惊动警察的前提下你可以偷得的最大钱数。

方法一:O(n)

动态规划,对于第 i 所房子有抢和不抢两种可能。
如果偷,则第 i - 1 所不能偷;如果不偷,则问题与 i - 1 所房子一致。
所以 dp[i] = max( dp(i - 1), dp[i - 2] + nums[i]):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len == 0) return 0;
if (len == 1) return nums[0];

int[] bestSum = new int[len];
bestSum[0] = nums[0];
bestSum[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; i++)
bestSum[i] = Math.max(bestSum[i - 1], bestSum[i - 2] + nums[i]);

return bestSum[len - 1];
}
}

方法二:O(1)

动态规划,如方法一分析,在计算第 i 所房子时,只需要偷与不偷第 i - 1 所房子可得到的最大值两个临时变量即可,因为:
dp[i - 1] = take(i - 1)
dp[i - 2] = notake(i - 1)
dp[i] = max( dp(i - 1), dp[i - 2] + nums[i]) = max( take(i - 1), notake(i - 1) + nums[i])
而 take(i) = notake[i - 1] + nums[i],notake(i) = dp[i - 1]。
从 1 所房子一直循环到 sums.length 所房子,每次循环计算当前房子的take和notake,以及maxSum。下次循环时, newTake = notake + sums[i],newNoTake = maxSum,newMaxSum = Math.max(take, notake):

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int rob(int[] nums) {
int take = 0, notake = 0, maxSum = 0;
for (int i = 0; i < nums.length; i++) {
take = notake + nums[i];
notake = maxSum;
maxSum = Math.max(take, notake);
}
return maxSum;
}
}

参考:
http://www.meetqun.com/thread-8777-1-1.html