p198

发表于 | 分类于 |

LeetCode p198 Combinations 题解

1.题目：

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.

题意：

小偷偷东西的问题，输入一个数组，小偷不能偷相邻的两家，问小偷最多能偷多少钱。

2.解题思路:

dp..空间复杂度其实可以更小，但是这样容易理解一些。
递归公式见代码注释。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
		if (len == 0)
			return 0;
		if (len == 1)
			return nums[0];
		int[][] list = new int[len + 1][2];
		for (int i = 1; i <= len; i++) {
			list[i][0] = Math.max(list[i - 1][0], list[i - 1][1]);// 到此为止i-1位置上不偷
			list[i][1] = nums[i - 1] + list[i - 1][0];// 偷i-1这个位置上的
		}
		return Math.max(list[len][0], list[len][1]);
    }
}

4.一些总结：