House Robber 分类: leetcode 算法 2015-07-09 20:53 2人阅读 评论(0) 收藏

DP

对于第i个状态(房子),有两种选择:偷(rob)、不偷(not rob)

递推公式为:

f(i)=max⎧⎩⎨⎪⎪{f(i−1)+vali,f(i−2)+vali,robi−1==0robi−1==1f(i−1),robnot rob

f(i)为动态规划表(DP表)(状态i下的最优解)

val为每间房子里的钱(val表)

rob为记录是否已经偷过,0表示没偷过,1表示偷了(is_robbed表)。

有了递推公式代码就很好写了

class Solution:
# @param {integer[]} nums
# @return {integer}
def rob(self, nums):
val=[0]+nums
DP=[0]*(len(nums)+1)
is_robbed=[0]*(len(nums)+1)
for i in range(1,len(val)):
if is_robbed[i-1]==0:
f_rob=DP[i-1]+val[i]
else:
f_rob=DP[i-2]+val[i]
f_no_rob=DP[i-1]
if f_rob>f_no_rob:
DP[i]=f_rob
is_robbed[i]=1
else:
DP[i]=f_no_rob
is_robbed[i]=0
return DP[len(nums)]

版权声明:本文为博主原创文章,未经博主允许不得转载。

上一篇:GNU project C


下一篇:svn+apache搭建版本控制服务器