Leetcode房子劫匪

我試圖House Robber問題（dp問題）上的代碼。來自用戶GYX的解決方案看起來簡單而優雅。Leetcode房子劫匪

int rob(vector<int>& num) { 
    int n = num.size(); 
     if (n==0) return 0; 
     vector<int> result(n+1,0); 
     result[1] = num[0]; 
     for (int i=2;i<=n;i++){ 
      result[i] = max(result[i-1],result[i-2]+num[i-1]); 
     } 
     return result[n]; 
    }

但我只是無法讓我的頭在邏輯。請幫助我理解邏輯，以及如何解決這樣的問題？

來源

2016-09-17 roang

假設我在house[k]中存儲第k個房屋的金額。

現在假設我在max[k]中儲存了可能從最初的k個房屋（和僅前k個）中掠奪的最大金額。

現在考慮沒有房子，所以max[0]=0

現在只考慮第一個房子，max[1] =在家裏量1

現在首先考慮2房，

max[2] = {要麼max[1]（意味着我們選擇贓物房屋1）或（房屋2的金額+我搶劫的房屋的最大金額，直到房子位於我目前住宅的2個地方）} = {max(max[1],house[2]+max[0])}

類似的前3棟房屋，max[3]=max(max[2],house[3]+max[1])

觀察這一趨勢，可以制定max[k]=max(max[k-1],house[k]+max[k-2])。這個值直到最後沒有更多的房子時才計算，我們從這些前n個房屋中獲得可以被搶劫的最大金額。

只有在以前有過一些練習和熟悉之後，DP問題纔會成爲頭等大事，而這總是有所幫助。

來源

2016-09-17 02:03:30 brijs

基本上答案是f(n) = max(f(n-1), f(n-2) + arr[n])，你問爲什麼。

讓我們假設這個數組和f(n)是函數。

當數組只有[9]，你的最大f(0)將arr[0]。

當數組爲[9,1]，你的最大f(1)是max(arr[0], arr[1])。

當數組是[9,1,7]，如果選擇7，你不能選擇因此1f(n-2) + arr[n]。但是，如果您未選擇7，則最大f(2)將與f(1)相同，即f(n-1)。

當陣列是[9,1,7,9]，則需要降二者1 & 7和選擇9,9 f(n) = max(f(n-1), f(n-2)+arr[n])方程滿足這種情況下。

來源

2017-05-20 23:12:22 Aaron

Leetcode房子劫匪

回答

相關問題