Skip to content

Latest commit

 

History

History
86 lines (60 loc) · 3.08 KB

0198-house-robber.adoc

File metadata and controls

86 lines (60 loc) · 3.08 KB
Raw

198. House Robber

{leetcode}/problems/house-robber/[LeetCode - 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.

思路分析

假设 f(k) = 从前 k 个房屋中能抢劫到的最大数额，Ai = 第 i 个房屋的钱数。

当 n=1 时，显然 f(1) = A1。

当 n=2 时，f(2) = max(A1, A2)。

当 n=3 时，有两种选项：

  1. 将第三个房间金额和第一个房间金额相加；

  2. 不算第三个房间，保持当前最大金额。

于是，可以总结出公式: \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。

剩下的工作就好办了。

让 D瓜哥 使用 动态规划的模式 来重新解读一下：

  1. 刻画一个最优解的结构特征：求解抢劫金额最大值。

  2. 递归地定义最优解的值： \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。

  3. 计算最优解的值，通常采用自底向上的方法：D瓜哥也按照动态规划（注意表格）的方式来实现，采用自底向上+备忘录的方式来求解，创建一个长度为 n+1 的数组，第 i 个元素表示到第 i 个房间为止，最大抢劫金额；则第 0 个元素为 0，第 1 个元素为 A1。然后根据上述公式定义，以此类推……

  4. 利用计算出的信息构造一个最优解。这一步不需要，暂时忽略。

使用递归、递归+备忘录、自底向上+备忘录，自底向上+简化备忘录四种方式分别实现。

一刷
link:{sourcedir}/_0198_HouseRobber.java[role=include]
二刷
link:{sourcedir}/_0198_HouseRobber_2.java[role=include]