1 題目描述

假設您是一個老練的盜賊，計劃沿著街道進行打家劫舍。該街道每家都存著一定數額的錢，而阻止您進行盜竊的唯一屏障是相鄰兩家的防盜系統是連接的，若相鄰兩家在同一晚都發生了盜竊案，該系統會自動通知到警察。

現在給定一個非負整數數組，代表該街道沿線每家的金錢數額，請計算在不觸發系統通知警察的情況下，您今晚能盜竊的最大金錢數額。

例子1：

輸入：[1,2,3,1]

輸出：4

釋義：先盜第1家，盜竊金錢1，然後再盜第3家，盜竊金錢3，總數為1 + 3 = 4。

例子2：

輸入：[2,7,9,3,1]

輸出：12

釋義：分別去盜第1、3、5家，盜竊總金額為2 + 9 + 1 = 12。

題目出處：

https://leetcode.com/problems/house-robber/

2 解決思路

逆向思考，先站在最後一家門口算一算，盜與不盜的最大利益。

這家盜的最大金額為：截至到上上家盜取的最大金額 + 這家的金額

這家不盜的最大金額為：截至到上一家盜取的最大金額

以此類推，直至遞歸到第1家，或第0家（空）。

因遞歸時用到的很多子計算是重複的，我們使用table存取截至到第i家盜取的最大金額，首次計算後寫入，再次需要時直接返回，實現加速。

3 Golang實現代碼

https://github.com/olzhy/leetcode/blob/master/198_House_Robber/test.go

原文連結：https://leileiluoluo.com/posts/leetcode-house-robber.html

本文作者：磊磊落落的博客，原創授權發布