2024.05.03 - House Robber

[wlsgh7608]

문제 - 링크

내가 현재 할 수 있는 경우의 수

• 이번에 내가 터는 경우(한 칸 건너뛰고 최대의 금액을 얻는 경우)
• 이번에 내가 털지 않는 경우(이전의 최대 금액)�

dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);

아래에서 부터 채워나가기

for (int i = 2; i <= N; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);
}

코드

class Solution {
    public int rob(int[] nums) {
        int N = nums.length;

        // 0-base => 1-base
        int[] newNums = new int[N + 1];
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            newNums[i] = nums[i - 1];
        }

        dp[1] = newNums[1];

        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);
        }

        return dp[N];


    }
}

시간, 공간 복잡도

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

실행 시간