原题链接
https://leetcode.com/problems/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.
Example 1:
Input: [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: [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.
这个题目的大意是:
你是一个计划沿着街道抢劫房屋的专业抢劫犯。每栋房子都有一定数量的钱被藏起来，唯一阻止你抢劫它们的限制是相邻的房子都有安全系统连接，如果两个相邻的房子在同一个晚上被闯入，它会自动联系警察。
给出一个非负整数的列表，代表每个房子的钱的数量，确定你今晚可以抢劫的最大金额，而不需要报警。
从给出的例子中可以分析出，这个Robber不能抢劫连续的房屋，即从数组中不能累加连续的数组元素。
换句话说，就是在一个给定的非负整数数组中，找出不连续的元素求和，使得和最大。
[算法设计]
package com.bean.algorithmexec;public class HouseRobber {public static int rob(int[] nums) {//如果数组的长度小于或者等于1的情况：数组中没有元素，则返回0；数组中只有一个元素时，就返回该元素的值。if (nums.length <= 1)return nums.length == 0 ? 0 : nums[0];//last表示上一次的最大值，初始时将数组中的第一个元素赋值给lastint last = nums[0];//now表示当前的最大值，初始时要决定是从数组中的第一个元素开始，还是第二个元素开始。int now = Math.max(nums[1], nums[0]);for (int i = 2; i < nums.length; i++) {//把现在的now暂存起来int tmp = now;//找到新的now最大值now = Math.max(last + nums[i], now);//找到之后，由于有了新的now，那么暂存的now就变成了lastlast = tmp;}return now;}public static void main(String[] args) {// TODO Auto-generated method stub//int[] nums=new int[] {1,2,3,1};int[] nums=new int[] {1,5,3,8,7,10,1,1,10};int result=rob(nums);System.out.println("RESULT = "+result);}}
输出结果：
RESULT = 33
另外一种算法设计
public static int rob2(int[] nums) {if (nums==null || nums.length==0){return 0;}if (nums.length==1){return nums[0];}if (nums.length==2){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(nums[i]+dp[i-2],dp[i-1]);}return dp[nums.length-1];}结果同上。