[LeetCode#198] House Robber

2025. 1. 9. 17:44·Algorithm/문제풀이

 

❐ Description


문제 링크 https://leetcode.com/problems/house-robber/description/
난이도 Medium(실버2~1)

최초에 DFS로 풀이를 했었는데 Time Limit Exceed가 발생했다. 이 문제를 해결하는 과정에서 Memoization을

다시 제대로 학습하게 됐으며, 이 문제를 시작으로 보다 다양한 DP 문제를 풀어봐야겠다.

 

 

 

 

 

❐ Solutions


1. Reculsive Ⅰ - Time Limit Exceed

public class Solution {

    private int answer = 0;

    public int rob(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            dfs(i + 2, nums, nums[i]);
        }
        return answer;
    }

    public void dfs(int startIdx, int[] nums, int prev) {
        if (startIdx > nums.length - 1) {
            answer = Math.max(answer, prev);
            return;
        }

        if (startIdx == nums.length - 1) {
            answer = Math.max(answer, prev + nums[startIdx]);
            return;
        }

        for (int i = startIdx; i < nums.length; i++) {
            dfs(i + 2, nums, nums[i] + prev);
        }
    }
}

 

2. Reculsive Ⅱ - Time Limit Exceed

public class Solution {
    public int rob(int[] nums) {
        return rob(nums, nums.length - 1);
    }
    
    private int rob(int[] nums, int i) {
        if (i < 0) return 0;
        return Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
    }
}
  • `rob(nums, i - 2) + nums[i]` :  `i`번째 집을 턴 경우
  • `rob(nums, i - 1)` : `i`번째 집을 털지 않은 경우

 

3. Reculsive + Memoization(top-down)

public class Solution {

    private int[] memo;
    
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return rob(nums, nums.length - 1);
    }

    private int rob(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo[i] != -1)return memo[i];
        memo[i] = Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
        return memo[i];
    }
    
}

 

 

4. Iterative + memo (bottom-up)

public class Solution {
    
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] memo = new int[nums.length + 1];
        memo[0] = 0;
        memo[1] = nums[0];
        
        for (int i = 2; i <= nums.length; i++) {
            memo[i] = Math.max(nums[i - 1] + memo[i - 2], memo[i - 1]);
        }
       
        return memo[nums.length];
    }

}

 

 

5. Iterative + two variables (bottom-up) 

public class Solution {
    
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        
        // prev2 = 두 집 전까지의 최대 금액
        // prev1 = 바로 직전 집까지의 최대 금액
        int prev2 = 0; prev1 = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // current = 현재(i번째) 집을 털거나, 털지 않는 두 경우의 최대값.
            int current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
}
  • prev2 ⇨ 두 집 전까지의 최대 금액
  • prev1 ⇨ 바로 직전 집까지의 최대 금액
  • current ⇨ 현재(i번째) 집을 털거나, 털지 않는 두 경우의 최댓값

 

 

 

 

 


'Algorithm > 문제풀이' 카테고리의 다른 글

[LeetCode#300] Longest Increasing Subsequence  (0) 2025.01.15
[LeetCode#151] Reverse Words in a String  (0) 2025.01.13
[LeetCode#128] Longest Consecutive Sequence  (0) 2025.01.07
[LeetCode#875] Koko Eating Bananas  (0) 2025.01.03
[LeetCode#1631] Path With Minimum Effort  (0) 2024.12.23
'Algorithm/문제풀이' 카테고리의 다른 글
  • [LeetCode#300] Longest Increasing Subsequence
  • [LeetCode#151] Reverse Words in a String
  • [LeetCode#128] Longest Consecutive Sequence
  • [LeetCode#875] Koko Eating Bananas
gilbert9172
gilbert9172
gilbert9172 님의 블로그 입니다.
  • gilbert9172
    バックエンド
    gilbert9172
  • 전체
    오늘
    어제
    • All Categories (173)
      • 우테코 7기 (21)
        • 1주차 (8)
        • 2주차 (5)
        • 3주차 (6)
      • Langauge (4)
        • Java (3)
        • Kotlin (1)
      • Back-End (13)
        • SpringBoot (1)
        • Trouble Shooting (0)
        • Setup & Configuration (1)
        • SQL (3)
        • Redis (8)
      • Architecture (6)
        • Multi Module (1)
        • DDD (5)
      • CS (30)
        • Data Structure (6)
        • Operating System (0)
        • Network (12)
        • Database (10)
        • Design Pattern (2)
      • Algorithm (78)
        • 내용 정리 (18)
        • 문제풀이 (60)
      • DevOps (6)
        • AWS (5)
        • Git (1)
      • Front-End (1)
        • Trouble Shooting (1)
      • Project (6)
        • 페이스콕 (6)
      • Book (7)
        • 이벤트 기반 마이크로서비스 구축 (6)
        • 친절한 SQL 튜닝 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Back-Tracking
    binarysearch
    오블완
    sliding-window
    부분단조성
    Two-Pointer
    greedy
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
gilbert9172
[LeetCode#198] House Robber
상단으로

티스토리툴바