My answer with python O(n), m[i] = max(m[i-1], m[i-2]+num[i])


  • 0
    D

    def rob(self,num):
        length = len(num)
        if length == 0:
            return 0
        elif length == 1:
            return num[0]
        elif length == 2:
            return max(num[0], num[1])
        m = []
        m.append(num[0])
        m.append(max(num[0],num[1]))
        i = 0
        for i in range(2, length):
            m.append( max(m[i-1], num[i]+m[i-2]) )
        return m[length-1]

Log in to reply
 

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