LeetCode 198 - House Robber - 题解/Solution

https://leetcode.com/problems/house-robber/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 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.
*
* @author dongyuxi
*
*/
public class Solution {
public int rob(int[] nums) {
if (null == nums || 0 == nums.length) {
return 0;
}
if (1 == nums.length) {
return nums[0];
}
if (2 == nums.length) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[nums.length];
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 - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}


支付宝 微信
文章目录