search

seungriyou / algorithm-study

알고리즘 & SQL 문제 풀이 기록
https://leetcode.com/u/summer_y
0 stars 0 forks source link

[LC] 198. House Robber #95

Open seungriyou opened 3 months ago

seungriyou commented 3 months ago

https://leetcode.com/problems/house-robber/

Approach

Idea 1: 1D DP

인접한 집을 털면 안 되기 때문에 nums[i] 까지 확인했을 때 가능한 가장 큰 금액은

  1. nums[i]를 택하지 않는 경우: nums[i - 1]까지 확인했을 때의 가능한 가장 큰 금액
  2. nums[i]를 택하는 경우: nums[i - 2]까지 확인했을 때의 가능한 가장 큰 금액 + nums[i]

중에서 더 큰 값이다.

따라서 이전에 구했던 값을 사용해야 하므로 다음과 같이 DP 테이블을 작성할 수 있다.

corner case를 고려하기 위해 dp[0]에는 0을 추가해줬다.

dp[i]: nums[i - 1]까지 확인했을 때 가능한 가장 큰 금액

DP 로직은 다음과 같이 작성할 수 있다.

for i in range(2, n + 1):
    # (1) 이전 집을 털 때와 (2) 그 이전 집을 털고 현재 집을 털 때 중 더 큰 값 기록
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])


Idea 2: O(1) Space DP

1D DP에서 dp[i]를 구할 때 dp[i - 1]과 dp[i - 2]만 확인하므로, 이를 O(n) space 리스트로 관리할 필요 없이 O(1) space 변수로 관리할 수 있다.

def rob(self, nums: List[int]) -> int:
    """O(1) space DP"""

    a, b = 0, 0
    for num in nums:
        a, b = b, max(a + num, b)

    return b


Complexity