Record my own stupidity. 20200530
whispering:too hard
问题描述:
偷盗相邻的house会触发警报,求解在不触发警报的情况下可以偷盗的最大价值。(跟粉刷房子的问题类似)
问题设定:
给定数组house_values:代表每个house内可偷盗的价值,value in values非负。
本问题可以使用暴力解法,穷举所有偷盗的可能性,并记录每种情况所有偷的价值即可。这里不进行赘述,主要记录DP求解。
DP问题的三个步骤
1.问题分解(将问题分解为重复子问题)
2.状态定义(为问题设定有效的状态)
3.DP方程(状态转移方程,求解第i个子问题与其他子问题的相关关系)
使用二维DP问题的求解方式,使用二维数据不仅记录当前状态的最大值,还需要记录当前house是否被偷。数组size为n*2
def house_robber(values):
"""
input:
values: house values
return:
res: the max value
"""
# boundary check
if not values:
return 0
if len(values) == 1:
return values[-1]
# state define (2 dims) size = n*2
# 0: not steal 1: steal
a = [[0]*2 for _ in range(len(values))]
a[0][0] = 0
a[0][1] = values[0]
for i in range(1,len(values)):
a[i][0] = max(a[i-1][0], a[i-1][1])
a[i][1] = a[i-1][0] + values[i]
return max(a[-1][0], a[-1][1])
为了降低空间复杂度,使用一维数组进行问题简化,记录当前状态i对应的house能获得的最大value,取出最大值。
def house_robber_(values):
"""
input:
values: house values
return:
res: the max value
"""
# boundary check
if not values:
return 0
if len(values) == 1:
return values[-1]
if len(values) == 2:
return max(values[0], values[1])
# state define (1 dim) size = n*1
a = values # (state init)
a[1] = max(values[0], values[1])
for i in range(2,len(values)):
a[i] = max(a[i-2] + values[i], a[i-1])
return a[-1]
观察两种求解的DP方程,可以看出状态i
的推导,只跟状态i-1
和i-2
有关。因此,有大佬仅使用两个状态值得转换就可以完成本问题的求解。
def rob(values):
"""
input:
values: house values
return:
res: the max value
"""
# boundary check
if not values:
return 0
if len(values) == 1:
return values[-1]
if len(values) == 2:
return max(values[1], values[0])
pre_ = values[0]
# 对于状态的定义是 当前所在位置可以偷盗的最大值
cur_ = max(values[1], values[0])
for i in range(2,len(values)):
tmp = max(pre_+values[i], cur_)
pre_ = cur_
cur_ = tmp
return cur_
house_robber_2:假设数组的收尾相连,那么对于数组的考虑就不能从现有的思路考虑,也就是数组被分为两个部分,取头不取尾values[:-1]
,或者取尾不取头values[1:]
。代码的话跟上面类似,这里只给出利用第三种方式的解法。
def rob(values) :
"""
input:
values: house values
return:
res: the max value
"""
# boundary check
if not values:
return 0
if len(values) == 1:
return values[-1]
if len(values) == 2:
return max(values[1], values[0])
if len(values) == 3:
return max(max(values[0],values[1]),max(values[1],values[2]))
pre_0 = values[0]
# 对于状态的定义是 当前所在位置可以偷盗的最大值
cur_0 = max(values[1], values[0])
pre_1 = values[1]
# 对于状态的定义是 当前所在位置可以偷盗的最大值
cur_1 = max(values[1], values[2])
for i in range(2,len(values)):
if i == 2:
tmp = max(pre_0+values[i], cur_0)
pre_0 = cur_0
cur_0 = tmp
elif i == len(values)-1:
tmp = max(pre_1+values[i], cur_1)
pre_1 = cur_1
cur_1 = tmp
else:
tmp_0 = max(pre_0+values[i], cur_0)
pre_0 = cur_0
cur_0 = tmp_0
tmp_1 = max(pre_1+values[i], cur_1)
pre_1 = cur_1
cur_1 = tmp_1
return max(cur_0,cur_1)
网友评论