聪明的小偷

Robber

有个聪明的小偷，打算偷一连串的房间。为了不被人发现，相邻的房间最多只偷一个。假设每个房间的价值为a[i]，问最大能偷取的价值。

如果价值都大于0，那么对于每间房间有两种情况，要么不偷，要么偷（此时不能偷前面一家），则存在递推公式如下：

dp[i] represents best value for robber to rob a[0..i]
dp[i] = max(dp[i-1], dp[i-2]+a[i])

如果存在价值小于0的，那么对于该房间选择显然是不偷的，此时：

dp[i] = max(dp[i-1], dp[i-2] + c) c = a[i] if a[i] > 0 else 0

1
def rob(self, nums):
    dp = deque([0] * 2)
    for i, num in enumerate(nums):
        c = num if num > 0 else 0
        val = max(dp[-1], dp[-2]+c)
        dp.popleft()
        dp.append(val)
    return dp[-1]

Robber2

聪明的小偷发现相邻房间不偷还是不安全，更改条件为相邻k家都不能偷，问此时能得到的最大价值。

如果还是采用第一种办法，由于需要获得相邻k家的最大值。时间复杂复杂度将是n*k。
dp(i) = max(dp(i-k)+a[i], max{dp(j)}) j = i-k+1 to i-1
为了避免每次找出临近k家的最大值，可以维护最大长度为k的递减队列，它的队首即为临近k家的最大值
从而避免了获取最大值的O(k)，复杂度为O(n)

1
def robber2(a, k=3):
	dp = deque([0] * k)
	largek = deque([(0, 0)])
	for i, v in enumerate(a):
		val = max(dp[0]+v, largek[0][0])
		dp.append(val)
		dp.popleft()
		# maintain a decrease queue for recent kth dp value
		while largek and largek[-1][0] < dp[-1]:
			largek.pop()
		largek.append((dp[-1], i))
		if largek[0][1]+k < i:
			largek.popleft()
	return dp[-1]

Robber3

聪明的小偷发现数目3n的小区，这次他带着两个学徒，每当他偷取了一间房间后，相邻的两个房间将被学徒偷走。问最大偷取价值。

对偷取房间进行了限制，进行dp时，需要增加一个变量，记录偷的房间数目，确保最后偷了n次。
需要对偷取第一间房进行特殊处理，确保不能偷取最后一间房。

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

1
'''
dp[i][j] represents the maximum value the robber can get from house[0..i-1] and stole j of them
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+a[i-1]) 
'''
def rob(a, chooseFirst):
	n = len(a)
	dp = [[0 for j in range(n/3+1)] for i in range(n+1)]
	c = 0 if chooseFirst else 1
	if chooseFirst:
		dp[1][1] = a[0]
	for i in range (2, n+c):
		for j in range(1, min(i, n/3+1)):
			dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+a[i-1])
	return dp[-1][-1]

def robber3(a):
	return max(rob(a, False), rob(a, True))