這篇page是針對leetcode上的198.打家劫舍所寫的。小尼先簡單的說明一下這道題的意思，就是有幾個房間是連續的，每個房間里面都可以偷一定的現金，然后如果兩個相鄰的房間被同一個晚上被偷了，那么系統就會自動報警，需要得到再不報警的前提下，我們可以偷到的最大的金額是多少。

小尼簡單的跟大家分析一下小尼對這道題的看法，其實這道題就是一個簡單的動態規劃的問題，其實就是需要我們分析出最佳的結果，我們分析一下dp五部曲：

1、確定dp數組以及下標的含義：dp[i]包含下標i以內的防務，最多可以偷竊的金額為dp[i]

2、確定遞推公式：就是決定dp[i]的因素就是第i個房間偷還是不偷，如果此時我們偷第i個房間，那么dp[i] = dp[i-2] + nums[i]，即：第i-1房一定是不考慮的，找出下標i-2以內的房，得到最多可以偷竊的金額；如果我們不偷第i個房間，那么dp[i] = dp[i-1]，即考慮第i-1個房，然后我們只需要在這兩個房間里取到最大值：即dp[i] = max(dp[i - 2] + nums[i] , dp[i - 1])

3、dp數組如何初始化：很顯然,dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

4、確定遍歷順序：dp[i]是根據dp[i - 2]和dp[i - 1]推導出來的，那么我們可以知道遍歷順序一定是從前往后遍歷的

5、最后就是我們需要推導出dp數組

小尼接下來拉一下這道題的解題的代碼：

class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];} }

小尼簡單的分析說明一下上面的代碼，其實就是像小尼上面所說的一樣，我們先初始化我們的dp數組，然后我們在去對我們的dp數組進行對應的一個遍歷，其實這個遍歷的順序和條件還是比較簡單的，最后我們是需要返回我們的目標值即可。

希望上面的分析和代碼可以幫助到小伙伴們~~~

總結

以上是生活随笔為你收集整理的My Eighty-first Page - 打家劫舍 - By Nicolas的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。