House Robber

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 & analysis

• Recursive
• Brute-force
• DP

Code

C++ - Bruteforce & Recursive : TLE

• 모든 해를 찾음

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        return robFrom(0, nums);
    }
    
    int robFrom(int i, vector<int>& nums) {
        if (i >= nums.size()) return 0;
        
        // Rob
        int robNext = robFrom(i + 1, nums);
        
        // No Rot
        int robCurrent = nums[i] + robFrom(i + 2, nums);
        
        // Return Maximum
        return max(robNext, robCurrent);
    }
};

• Recursive Process

robFrom(0) -> 최대값 = max(robFrom(1), nums[0] + robFrom(2))
  robFrom(1) -> 최대값 = max(robFrom(2), nums[1] + robFrom(3))
    robFrom(2) -> 최대값 = max(robFrom(3), nums[2] + robFrom(4))
      robFrom(3) -> 최대값 = max(robFrom(4), nums[3] + robFrom(5))
        robFrom(4) -> 최대값 = max(robFrom(5), nums[4] + robFrom(6))
          robFrom(5) -> 0 (nums의 범위를 벗어남)
          robFrom(6) -> 0 (nums의 범위를 벗어남)
        robFrom(4) 결과: max(0, 1 + 0) = 1
      robFrom(3) 결과: max(1, 3 + 0) = 3
    robFrom(2) 결과: max(3, 9 + 1) = 10
  robFrom(1) 결과: max(10, 7 + 3) = 10
robFrom(0) 결과: max(10, 2 + 10) = 12

C++ - DP

• 집을 털지 안털지를 선택 : rob or not

code 1

• Time Complexity : O(n)
• Space Complexity : O(n)
• DP 메모리에 저장

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[n-1];
    }
};

Code2

• Time Complexity : O(n)
• Space Complexity : O(1)
• Pointer 2개를 이용하여 최소한의 값만 저장

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int prev1 = max(nums[0], nums[1]);
        int prev2 = nums[0];

        for (int i = 2; i < n; ++i) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

Testcase

Input:

[114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240]

Ouput:

>>
4173