LeetCode - House Robber

문제 설명

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.

제약사항

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

Solution

[전략]
DP 접근법을 이용
1. 각 단어를 HashMap으로 저장하고
2. 문자열 s를 0번째부터 j번째까지 잘라서 HashMap에 저장된 단어인지 확인

• 저장된 단어이면 0번째-j번째 자른 문자열에 대해 사전에 등록된 단어임을 기록 2차원 배열에 기록
• 저장되지 않은 단어이면 false 저장

3. 문자열 시작점(i)을 1씩 증가하며, 문자열 s의 0번째-i-1번째가 사전에 등록된 단어들로 구성되어 2차원 배열에 true로 기록된 경우에만 2번 과정을 반복

class Solution {
    public int rob(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        int twoPrevSum = nums[0];
        int prevSum = Math.max(nums[0], nums[1]);
        int sum = prevSum;

        for (int i = 2; i < nums.length; i++) {
            sum = Math.max(twoPrevSum + nums[i], prevSum);
            twoPrevSum = prevSum;
            prevSum = sum;
        }

        return sum;
    }
}