213. 打家劫舍 II

总结:
	简简单单动态规划,和字符串一样,看以当前元素结尾所能取到的最大值
	没什么好说的,注意是一个圈所以第一个元素和最后一个元素不共存,所以可以
	分为两种情况,有一无后,有后无一

'''
    注意:
        房屋被围成了一圈,所以第一个和最后一个一定不会同时出现
        假设出现第一个不出现最后一个
            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					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5638034.html