(LeetCode) 198. House Robber

198. House Robber

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Dynamic Programming
• 난이도 : Medium

Problem

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

Exapnder

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums.first()
        }
        nums[1] = Math.max(nums[0], nums[1])

        for (i in 2 until nums.size) {
            nums[i] = Math.max(nums[i] + nums[i - 2], nums[i - 1])
        }
        return nums.last()
    }
}

Point of Thinking

• nums는 1개 이상의 원소를 가지고 있으므로 nums.size == 1 인 경우에만 엣지케이스 처리하면 된다.
• 인접한 두 개의 값을 활용하지 않는 범주내에서 최대 합을 구한다.
• 주어진 nums를 그대로 dp배열로 활용하면 된다. 여기서 index는 index까지의 최대 합을 뜻한다.
• 점화식은 문제 해석 그대로 처리하면 Accepted.

$f(n) = Max(f(n) + f(n - 2), f(n - 1))$