Dynamic programming,very easy python solution


  • 0
    L
    class Solution(object):
        def rob(self, nums):
            if len(nums) == 0:
                return 0
            if len(nums)<=2 and len(nums) != 0:
                return max(nums)
            # 动态规划
            mynum = [nums[0],max(nums[0],nums[1])]    # 使用一个list记录到当前位置最大的值
            for i in xrange(2,len(nums)):
                max_num = nums[i]+mynum[-2]
                if max_num >= mynum[-1]:
                    mynum.append(max_num)
                else:
                    mynum.append(mynum[-1])
            return mynum[-1]
    

  • 0
    W

    There is no need to add len(nums) != 0 in the second condition
    Also you could change

    if max_num >= mynum[-1]:
                    mynum.append(max_num)
                else:
                    mynum.append(mynum[-1])
    

    to

    mynum.append(max(max_num, mynum[-1])
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.