博客

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]

输出: 4

解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]

输出: 12

解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。

偷窃到的最高金额 = 2 + 9 + 1 = 12 。

首先，刚开始看这道题的时候，我想的是用奇数偶数去做，就是奇数抢的最高金额与偶数抢的最高金额去比较，谁高输出谁，后来运行结果不对，没考虑第一和最后一个房子的关系，初次代码如下：

package cn.ls.Test;

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = 0;
		int num = 0;
		int[] a = new int[n];
		for (int i = 0; i <n ; i++) {
			a[i] = sc.nextInt();

			if (i % 2 == 0) {
				sum += a[i];
			} else {
				num += a[i];
			}
		}
		if (sum >= num) {
			System.out.println(sum);
		} else {
			System.out.println(num);
		}
	}
}

后来想到了用动态规划去做这道题，动态规划方程：


dp[n] = MAX( dp[n-1], dp[n-2] + num )



n就代表从前个房屋中能抢劫到的最大数额,num就代表当前房屋的钱数(最后一个)，



dp[1]代表1号房，dp[n]代表n号房,dp[n-1]代表除了最后一间房前面所有房子能取得的最大金额，dp[n-2]+num



表示前n-2个房子能偷的最大的金额加上最后一个房子也可以叫做当前房子的金额，代码里也有说明，如下：



图解类比如下：



代码如下：


package cn.ls.Test;

import java.util.Scanner;

public class Test01 {
	 public int rob(int[] nums) { //接收数组
	        int len = nums.length;  //数组的长度
	        if(len == 0)
	            return 0;  
	        int[] dp = new int[len + 1]; //让dp[0]为0，长度比传来的数组多一个，正好对应上，为的是简化代码
	        dp[0] = 0;
	        dp[1] = nums[0]; //把第一个房子的钱给了dp[1];
	        for(int i = 2; i <= len; i++) {
	            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
	        }
	        return dp[len]; //返回最大金额
	    }
}