198. 打家劫舍 - 力扣（LeetCode）

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

示例 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 。提示：1 <= nums.length <= 100
0 <= nums[i] <= 400

算法設計

????????我們是如何辨識出這道題需要使用dp算法的呢？

? ? ? ? 首先我們需要理解題意，題目講述的是一個實際問題，我們需要進行一些數學抽象，層層刨析的看到問題的本質。

? ? ? ? 首先我們應該看到第一層：題目中雖然只說了相鄰房間不能同時打劫，但是我們應該理解為不能打劫相鄰房間，但打劫的房間不一定是以間隔1的形式出現的，也可以跳躍多個房間打劫下一個。

? ? ? ? 接著上面，我們應該分析出第二層：問題雖然簡單描述，但是可以想象為被相鄰規則直接禁止的房屋我們不能踏入花園，而未被相鄰規則禁止的房屋我們可以到花園外看兩眼，決定是否進行打劫。

? ? ? ? 接下來我們通過目前的狀態推測過去的情況，對于到達第i個房屋后的能打到的最大金額dp[i]

? ? ? ? 1.當我們目前選擇了打i時，之前絕對不可能打過i-1，所以有dp[i] = dp[i-2] + nums[i]

? ? ? ? 2.當我們不打i時，無非兩種情況，一種：確實打過了i-1，所以不能打i，二種：沒打i-1，但是也不計劃打i，以上兩種情況都可以用dp[i-1]來概括，然而究竟打不打i-1，這個需要根據dp[i-1]的相同方法分析才能得到，也就是遞推

? ? ? ? 綜上所述，為了在每個dp求得最大的金額，我們應該有狀態轉移方程：

? ? ? ? ? ? ? ? ? ? ? ? ? dp[i] = fmax(dp[i-2]+nums[i], dp[i-1])?

? ? ? ? 這樣我們就分析出它跟爬樓梯問題的一個共通點了，就是，達到i時的狀態都可以通過拆解為多種過去狀態分支。再把過去狀態與dp進行聯系，從而求得dp[i]

int rob(int* nums, int numsSize) {int dp[2];int temp;dp[0]=*(nums);if(numsSize==1){return dp[0];}if(numsSize>1){dp[1]=fmax(dp[0],*(nums+1));}if(numsSize>2){for(int i=2; i<numsSize; i++){temp=fmax(dp[0]+*(nums+i),dp[1]);dp[0]=dp[1];dp[1]=temp;}}return dp[1];
}

? ? ? ? 比如說如果我打了i的，那么我最近至少也得從dp[i-2]過來吧

? ? ? ? 再比如，我不打i，要么是因為我打了i-1所以不能打i，再要么是我不打i-1，只是在它門口鬼鬼祟祟地晃悠了兩圈，又來到i，其實我能打i，但是仔細考慮了一下不打i。

? ? ? ? 所以從語態角度講，這道題的狀態轉移條件劃分規則為在一般現在時下是否打i，而不是我是否能打i。所以打劫Ⅰ類問題與爬樓梯的區別在于，爬樓梯中狀態轉移方程的dp [i-1] 和 dp[i-2]爬到dp[i]講的是一個can的問題，描述了我上一次狀態到本次狀態的能力。而在打劫問題中，我們描述的是一個do的問題，以基本實時的分支為標準進行劃分，而通過對對立事件二存一的邏輯求得dp[i]。

? ? ? ? 為什么在打劫問題中需要以do的方式去思考呢？在以后我們如何從根本上辨別這兩種狀態轉移方式的應用場景？

? ? ? ? 以我看呀，爬樓梯問題的目標解是達成目的途徑數量，所以計算過程本質是把所有最簡對立事件的個數統計。而打劫問題，是一個結果驅動型問題，要求的是給定過程量的和最大，結果所對應的行為是固定的一種或多種。

? ? ? ? 不如我們先換一個問法，在題設條件下，不追求最大獲利，總共有多少種打劫方式？

? ? ? ? 假設dp_can[i]表示打劫到i總共的方式，

? ? ? ? 那么打劫到i有i種大可能性，即上一次打劫的是0，1，...，i-1；

? ? ? ? 那么

???????dp_can[i] = dp_can[i-2] +...+ dp_can[0]

? ? ? ? 很顯然dpcan[0]=1，因為打1只有小區大門開始一種方法；

? ? ? ? dpcan[1]=1;

????????dpcan[2] = dpcan[0]?= 1;

????????dpcan[3] = dpcan[0] + dpcan[1] = 2;

? ? ? ? ...

? ? ? ? 因此這更像是斐波那契數列的升級版，當前途徑狀態量是除前一元素先前途徑狀態量的和；

? ? ? ? 所以，dp最優問題是實質上是在dp決策問題上施加額外條件形成的，因為決策的形成帶動形成了解的結構，所以最優問題的解也是可以進行狀態轉移的。

????????
????????????????????????????????

????????

????????