每日算法题——打家劫舍

继续我们的每日算法题系列，有时候你不知道干嘛的时候来上两道算法题，真香～

话不多说，来看看今天的题目，感觉还是比较有意思的：

题目描述

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

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

示例1：

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例1：

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

这道题目是一道很典型的 “动态规划” 类算法题目，LZ我在动态规划这类题目上还是偏薄弱，动态规划的精髓就是状态转移方程，通常你遇到这类题目的时候，基本上都是 “找最优解”，“重叠子问题”，一般来说一个大的问题是可以拆成一个个子问题，下面我们来在线分析一下。

解题思路

首先我们来拆分问题，拆成最简单的来看：

1、当只有1间房的时候，我们没有选择，只能选择抢劫这间房；

2、当有两间房的时候，我们可以比较哪间房里面的钱多，抢劫钱多的房间就好了；

3、当有三间房的时候，有两种方案，抢1，3号房间/抢2号房间的，比较一下哪种方案多；

4、当有四间房的时候，因为我们已经知道了1，2，3间房时能获取到的最大金额，所以我们只需要将抢第四间房的金额数加上抢第二间房能获取到的最大金额数来和第三间房进行比较，取最大值就好了。

相信写到这里大家应该就能看出来状态转移方程是什么了吧，当我们抢劫第 i 间房的时候，我们需要比较一下第 i-2 间房所能获取到的最大金额数加上当前房间的金额数和第 i-1 间房所能获取到的最大金额数哪个大；我们用一个数组来保存抢劫金额的最大数，于是就有了，f[n] = Math.max(f[n-2] + money[n], f[n-1])

题解

public int rob(int[] nums) {
    if (null == nums || nums.length == 0) {
        return 0;
    }
    int len = nums.length;
    if (len == 1) {
        return nums[0];
    }
    if (len == 2) {
        return Math.max(nums[0], nums[1]);
    }
    //上述判断是将最简单的几种情况先计算好，也是为了初始化momey[0] 和 money[1]
    
    // 定义一个数组，用来保存打劫 0 - (len-1) 家最大能打劫到的金额数
    int[] money = new int[len];
    money[0] = nums[0];
    money[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < len; i++) {
        money[i] = Math.max(money[i - 2] + nums[i], money[i - 1]);
    }
    return money[len - 1];
}