1, 题目

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

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. 定义问题:
  2.     f(n) 是第n个房屋一定被打劫的收入
  1. object Solution {
  2.     def rob(nums: Array[Int]): Int = {
  3.         if (nums.length == 0) {
  4.             return 0
  5.         }
  6.         if (nums.length == 1) {
  7.             return nums(0)
  8.         }
  9.         var fn1 = nums(0)
  10.         var fn2 = nums(1)
  11.         var current_max_profit = fn1
  12.         for (i <- 2 until nums.length) {
  13.             val t = nums(i) + current_max_profit
  14.             fn1 = fn2
  15.             fn2 = t
  16.             current_max_profit = current_max_profit.max(fn1)
  17.         }
  18.         current_max_profit = current_max_profit.max(fn2)
  19.         current_max_profit
  20.     }
  21. }
  1. class Solution:
  2.     def rob(self, nums: List[int]) -> int:
  3.         if nums:
  4.             if len(nums) == 1:
  5.                 return nums[0]
  6.             else:
  7.                 fn1 = nums[0]
  8.                 fn2 = nums[1]
  9.                 current_max_profit = fn1
  10.                 for i in range(2, len(nums)):
  11.                     fn1, fn2 = fn2, nums[i] + current_max_profit
  12.                     current_max_profit = max(current_max_profit, fn1)
  13.                 current_max_profit = max(current_max_profit, fn2)
  14.                 return current_max_profit
  15.         else:
  16.             return 0