leetcode 198. House Robber

今天刷 leetcode 发现了大神操作，对于刚开始刷题的我只能膜拜一下，顺便写个随笔。

题目：

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:4Explanation: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:12Explanation: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.

简单说就是，你是个牛X小偷，不存在入室抢劫空手而归的情况。唯一的难题就是一天晚上不能连着强两个房子的钱，否则警报就会触发。每间房子有固定数量的钱，然后需要做的是求最大的一天晚上你能抢多少钱并且不会触发警报。

看一下大神思路：

https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.

动态规划的题就是先做出暴力递归的方法，然后再用数组来代替递归。

第一步：找出递归关系

两个选择：偷这间房子和不偷这间房子。

偷：偷的话就是偷当前的房子和第 i-2 房子。

不偷：不偷就是偷 第 i-1 房子

所以递归依据 rob（i） = Math.max(rob(i - 2) + currentHourse, rob(i - 1));

第二步 代码：

第三步 将递归过的记住，避免重复计算：

第四步 取消递归：

第五步 降低空间复杂度：

就此就是最优解了，动态规划就是要一步一步的推，没有人能一下写成动态规划，虽然看了这个方法，下次再写动态规划可能还是抓瞎。但是多练习每天进步一点，总能看到效果。