[LeetCode] 198. House Robber - 문제풀이

Description

주어진 배열에서 연속된 위치의 값은 훔칠 수 없는 점을 감안하여 최대로 훔칠 수 있는 금액을 계산하는 문제입니다.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Solution 1. Dynamic Programing

public int rob(int[] nums) {
    int len = nums.length;
    if(len == 1){return nums[0];}
    if(len == 2){return Math.max(nums[0],nums[1]);}

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

동적프로그래밍을 통해서 bottom-up방식으로 풀어나갑니다. 먼저 재귀 관계를 찾아보면 현재위치i에서 집을 털 경우 이전집(i-1)은 털 수 없지만 그 이전집(i-2)의 누적된 금액은 다 가져갈 수 있습니다. 따라서 현재 위치에서 최대로 가져갈 수 있는 값은 이전위치(n-1)의 누적치와 현재위치(i)의 금액과 i-2위치의 누적금액의 합계금액중 최대 금액입니다.

Reference

House Robber - LeetCode