[Algorithm] LeetCode 198. House Robber in Python

💡 LeetCode 198:

인접하지 않은 집들을 털어 가장 많이 돈을 터는 경우의 최대합 구하기

🌱 코드 in Python

알고리즘: Dinamic Programing

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

'인접하지 않은', '최대합' => DP 문제였다.
나를 선택하지 않고 내 앞의 것을 선택하는 경우 = nums[i - 1]
내 앞의 것을 선택하지 않고 나와 내 앞앞 것을 선택하는 경우 = nums[i - 2] + nums[i]

이렇게 계속 nums 배열을 갱신해주었다.
nums[1]의 경우에만 자신과 바로 앞을 비교해주었다.

🧠 기억하자

1. 처음 풀 때 오 Dp! 하고 바로 DP 배열을 새로 만들어주었었다.
   그치만 그럴 필요가 없다. Nums 배열을 갱신하면 되니까. 잘 생각해보고 풀기 약속.

LeetCode 198 바로가기