查找可從N獲取的最大值

Question

有n個房屋（1,2,3，...，n）。小偷必須從房屋1開始，到達房屋n以最大限度地偷竊。他可以偷房子，他可以離開。如果他完全偷了房子，房主就會通知左邊和右邊的鄰居。多少最大可他偷..

我們如何通過動態規劃解決..

Answer 1

讓arr[0..n-1]表示端口的數量爲每個主機從1到n。

在每一點上，您有兩種選擇：掃描當前主機的所有端口或不掃描當前主機的端口。

讓dp[]成爲數組。

顯然，

dp[i] = max(dp[i-1], arr[i] + dp[i-2])

dp[i-1]當你不掃描的端口的情況。 arr[i] + dp[i-2]當您掃描當前主機的端口時。在這種情況下，由於無法掃描連續主機的限制，您無法添加dp[i-1]。所以我們加上dp[i-2]。

你最後的答案是dp[n-1]

希望它可以幫助！

編輯：下面是等同於你一個問題：

有建行，每個都包含在它的一些值N的房子。一個小偷會偷這些房屋的最大價值，但他不能在兩個相鄰的房子裏偷竊，因爲一個被盜房子的主人會告訴他的左右兩個鄰居。什麼是最大的被盜價值？

尋找解決方案here