Алгоритмический вопрос дня — литкод 198 — семейное ограбление — питон

【Название Описание】

【Идея кода】

Одномерное динамическое программирование, самое главное - найти уравнение перехода состояния и начальное состояние. Уравнение перехода состояния: либо перейти к предыдущему, либо перейти к первым двум и этому, в зависимости от того, что больше.

[код выше]

class Solution:
    def rob(self, nums: List[int]) -> int:
        if(len(nums)==0): return 0
        if (len(nums)==1):return nums[0]
        dp=[]
        dp.append(nums[0])
        dp.append(max(nums[0],nums[1]))
        for i in range(2,len(nums)):
            dp.append(max(nums[i]+dp[i-2],dp[i-1]))
        return dp[len(nums)-1]

Посмотрите на эффект, временная сложность линейного уровня