What is the best way to solve House Robber?

The optimized O(n) approach using 1D DP patterns is generally preferred.

상위 150개 인터뷰중간

집 강도

'House Robber' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

당신은 거리의 집을 털려는 전문 강도입니다. 각 집에는 일정량의 돈이 숨겨져 있으며, 각각의 집에서 물건을 강탈하는 것을 막는 유일한 제약은 인접한 집에 보안 시스템이 연결되어 있고 같은 밤에 인접한 두 집에 침입하면 자동으로 경찰에 연락한다는 것입니다.

각 집의 금액을 나타내는 정수 배열 숫자가 주어지면 오늘 밤 경찰에 신고하지 않고 훔칠 수 있는 최대 금액을 반환하세요.

rob(nums: List[int]) -> int 함수를 작성하세요.

제약

•1 <= len(nums) <= 100
•0 <= nums[i] <= 400

예

Example 1

Input

nums = [1,2,3,1]

Output

Explanation

Rob house 1 (money = 1) then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 2

Input

nums = [2,7,9,3,1]

Output

Explanation

Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total = 12.

Need a Hint?

세트나 힙과 같은 1D DP 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

1D DP 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def rob_opt(nums):
    rob1, rob2 = 0, 0
    for n in nums:
        temp = max(n + rob1, rob2)
        rob1 = rob2
        rob2 = temp
    return rob2

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def rob_brute(nums):
    def solve(i):
        if i >= len(nums): return 0
        return max(nums[i] + solve(i + 2), solve(i + 1))
    return solve(0)