有趣的基本DP问题(抢房子)

Question

小偷想抢房子。他知道每所房子里有多少钱。他不能连续抢三套房子。找出他能抢到的最多的钱。

示例：

6 5 5 10 100 10 5

5+10+100+5=120。

在此之后，我们可以推广，因为他不能掠夺k个连续的房子。

Answer 1

为了解决这个问题，你需要记住DP是在试图模仿一次详尽的搜索。在您的示例中，小偷需要为每一所房子选择是否应该洗劫它。他对他“访问过”的连续房屋的数量有一个额外的限制(这可以作为一个基本从句来处理，我发现它更容易遵循)。

这为我们提供了以下递归公式：

Base clause 1 for forbidden path:
T(i, 0) = -INFINITY   
Base clause 2 before looting any house:
T(0, c) = 0
Recursive formula:
T(i, c) = max { T(i-1, c-1) + loot[i] , T(i-1, k) }
                       ^                    ^
               loot i'th hourse       Skip i'th house

完成后，解决方案取决于某些1 <= c <= k的T(n,c)