# 0198. 打家劫舍 ## 題目地址(198. 打家劫舍) <https://leetcode-cn.com/problems/house-robber/> ## 題目描述 ``` <pre class="calibre18">``` 你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。 給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。 示例 1： 輸入：[1,2,3,1] 輸出：4 解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。 偷竊到的最高金額 = 1 + 3 = 4 。 示例 2： 輸入：[2,7,9,3,1] 輸出：12 解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。 偷竊到的最高金額 = 2 + 9 + 1 = 12 。 提示： 0 <= nums.length <= 100 0 <= nums[i] <= 400 ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - airbnb - linkedin ## 思路 這是一道非常典型且簡單的動態規劃問題，但是在這里我希望通過這個例子， 讓大家對動態規劃問題有一點認識。 為什么別人的動態規劃可以那么寫，為什么沒有用 dp 數組就搞定了。 比如別人的爬樓梯問題怎么就用 fibnacci 搞定了？為什么？在這里我們就來看下。 思路還是和其他簡單的動態規劃問題一樣，我們本質上在解決`對于第[i] 個房子，我們搶還是不搶。`的問題。 判斷的標準就是總價值哪個更大， 那么對于搶的話`就是當前的房子可以搶的價值 + dp[i - 2]` > i - 1 不能搶，否則會觸發警鈴 如果不搶的話，就是`dp[i - 1]`. > 這里的 dp 其實就是`子問題`. 狀態轉移方程也不難寫`dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);`（注：這里為了方便計算，令 `dp[0]`和 `dp[1]`都等于 0，所以 `dp[i]`對應的是 `nums[i - 2]`） 上述過程用圖來表示的話，是這樣的：  我們仔細觀察的話，其實我們只需要保證前一個 dp\[i - 1\] 和 dp\[i - 2\] 兩個變量就好了， 比如我們計算到 i = 6 的時候，即需要計算 dp\[6\]的時候， 我們需要 dp\[5\], dp\[4\]，但是我們 不需要 dp\[3\], dp\[2\] ... 因此代碼可以簡化為： ``` <pre class="calibre18">``` <span class="hljs-keyword">let</span> a = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> b = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">const</span> temp = b; b = <span class="hljs-params">Math</span>.max(a + nums[i], b); a = temp; } <span class="hljs-keyword">return</span> b; ``` ``` 如上的代碼，我們可以將空間復雜度進行優化，從 O(n)降低到 O(1), 類似的優化在 DP 問題中不在少數。 > 動態規劃問題是遞歸問題查表，避免重復計算，從而節省時間。 如果我們對問題加以分析和抽象，有可能對空間上進一步優化 ## 關鍵點解析 ## 代碼 - 語言支持：JS，C++，Python JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number} */</span> <span class="hljs-keyword">var</span> rob = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-title">// Tag: DP</span> <span class="hljs-keyword">const</span> dp = []; dp[<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; dp[<span class="hljs-params">1</span>] = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">2</span>; i < nums.length + <span class="hljs-params">2</span>; i++) { dp[i] = <span class="hljs-params">Math</span>.max(dp[i - <span class="hljs-params">2</span>] + nums[i - <span class="hljs-params">2</span>], dp[i - <span class="hljs-params">1</span>]); } <span class="hljs-keyword">return</span> dp[nums.length + <span class="hljs-params">1</span>]; }; ``` ``` C++ Code： > 與 JavaScript 代碼略有差異，但狀態遷移方程是一樣的。 ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">rob</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums)</span> </span>{ <span class="hljs-keyword">if</span> (nums.empty()) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> sz = nums.size(); <span class="hljs-keyword">if</span> (sz == <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">auto</span> prev = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">auto</span> cur = max(prev, nums[<span class="hljs-params">1</span>]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">2</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> tmp = cur; cur = max(nums[i] + prev, cur); prev = tmp; } <span class="hljs-keyword">return</span> cur; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">rob</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> length = len(nums) <span class="hljs-keyword">if</span> length == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> nums[<span class="hljs-params">0</span>] <span class="hljs-keyword">else</span>: prev = nums[<span class="hljs-params">0</span>] cur = max(prev, nums[<span class="hljs-params">1</span>]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, length): cur, prev = max(prev + nums[i], cur), cur <span class="hljs-keyword">return</span> cur ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [337.house-robber-iii](https://github.com/azl397985856/leetcode/blob/master/problems/337.house-robber-iii.md) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。