Leetcode House Robber

今天做网申题遇到的,一看就知道是动态规划。因为好久没碰算法题了,一看这题20分,就很紧张,想得很复杂。事后一看Leetcode,才发现这题是Easy…

ps:想解法的时候无聊,手贱点了一下交卷按钮,直接就交卷了…兄dei,一般点提交按钮不是会弹出个确认框吗!我大题还没写完,你就给我提交了…

参考:https://leetcode.com/problems/house-robber/description/

 

一、题目

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.

大概意思就是,现在有一个数组,求解数组中连续不相邻元素的和的最大值。举个例子,假如我选择了index为i的数字,那么我不能选相邻的数字i-1和i+1的数字了。

对于这种“让你纠结,选出一个最佳方案”的问题,首选动态规划。

二、分析

思路来自:http://blog.csdn.net/jonlylinux/article/details/78254983

看到这种动态规划题,一定要着眼于当下:“如果我这样做,会发生什么?”不要考虑太多别的东西,否则就会想得很复杂,反而做不出来。

假设已知 0, 1,2,3,n-1 个房屋的偷取方式能获得最大金钱dp(k),0 <= k <= n-1,那么在房屋数增加到n时,dp(n)如何用dp(k)来表示?

既然0至n-1是已知,那么在偷取第n个时:

  1. n不被偷取 dp(n) = dp(n-1)。
  2. n被偷取,那么n-1一定没被偷取 dp(n) = dp(n-2) + M(n)。

解释一下:

  1. 如果n不被偷取,那么我当前的最大收益就是dp(n-1)(之前的最大值,算到n-1为止),这个应该很好理解吧!
  2. 如果n被偷取了,那么n-1肯定不能偷取(因为相邻),那么我当前的最大收益就是dp(n-2)(之前的最大值,算到n-2为止,n-1不能算进去)+ M(n)(我这次偷到的钱)。

所以可以得出一个状态方程:

dp(n) = max(dp(n-1), dp(n-2) + M(n))

那么问题来了,这条方程有什么用?哼哼,我们的算法可以围绕着这条方程展开!

三、求解

1.解法一(根据方程求解)

HouseRobber1.java

运行结果为:

这种做法是最老实,也是最直观的。

2.解法二(更直观的解法,但是要转弯)

HouseRobber2.java

运行结果为:

这是我在Leecode上找到的推荐解答:

HouseRobber3.java

思想是一样的。

三、总结

偷懒不做题,很快就荒废了…这才是Easy的动态规划题,就想了我半天。主要是做得太少了,不懂套路…

发表评论

电子邮件地址不会被公开。 必填项已用*标注