总结:
简简单单动态规划,和字符串一样,看以当前元素结尾所能取到的最大值
没什么好说的,注意是一个圈所以第一个元素和最后一个元素不共存,所以可以
分为两种情况,有一无后,有后无一
'''
注意:
房屋被围成了一圈,所以第一个和最后一个一定不会同时出现
假设出现第一个不出现最后一个
dp[i]=nums[i-1]+dp[i-1] i=1,2,3,4...
dp[i]表示长度为i nums[i-1]表示下标为i-1
dp[0]=0
对于
'''
def fun1(nums):
if len(nums)<=3: #只能偷一个
return max(nums)
dp=[0]*(len(nums)+1)
max_1=0
dp[1]=nums[0]
dp[2]=nums[1]
for i in range(3,len(nums)):#从1到len(s)-2
dp[i]=nums[i-1]+max(dp[0:i-1:])#找到可取范围内的最大值
if max_1
def fun2(nums):
'''
上面代码是可以化简的,我每次使用的都是与i相隔一格的集合最大值
所以可以拿变量记录最大值,这样的话可以省去每次查找花费的时间
:param nums:
:return:
'''
if len(nums)<=3: #只能偷一个
return max(nums)
dp=[0]*(len(nums)+1)
max_1=0
dp[1]=nums[0]
dp[2]=nums[1]
pre1=dp[1]
for i in range(3,len(nums)):#从1到len(s)-2
dp[i]=nums[i-1]+pre1#找到可取范围内的最大值
if max_1
def fun3(nums):
'''
fun1是一个时间复杂度为o(n**2) 空间复杂度为o(n)的算法
fun2优化了时间复杂度变为o(n),采用变量记录,少了重复操作,空间复杂度没变
现在在fun2的基础上优化空间复杂度
:param nums:
:return:
'''
if len(nums)<=3: #只能偷一个
return max(nums)
max_1=max(nums[0],nums[1])
pre1=nums[0]
pre2=nums[1]
for i in range(3,len(nums)):#从1到len(s)-2
cur=nums[i-1]+pre1
if max_1
