House Robber

코딩 문제

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

오케이! 이건 LeetCode의 House Robber 문제야. DP(동적 계획법) 입문용으로 정말 많이 나오는 유명한 문제 중 하나야.

문제 파악

도둑이 집을 털려고 하는데, 조건이 있다
• 집들이 일렬로 쭉 있고
• 서로 인접한 집은 동시에 못 턴다 (보안 시스템 작동됨)
• 각 집마다 털 수 있는 금액이 정해져 있다 (nums 배열)

-> 인접한 집은 건너뛰면서, 최대 얼마까지 털 수 있는지 구해봐.

접근 방법 (DP)

이건 전형적인 “선택 or 선택 안함” DP 문제
• i번째 집을 턴다면?
→ i-2번째까지의 최댓값 + 현재 집 금액
• i번째 집을 안 턴다면?
→ 그냥 i-1번째까지의 최댓값 유지

점화식 : dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

코드 구현

import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        if (nums.length > 1) {
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < nums.length; i++) {
                dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            }
        }
        return dp[nums.length-1];
    }
}