Leetcode - 198. House Robber 풀이

문제

프로페셔널 도둑에게 훔칠수 있는 돈이 기록된 집의 리스트 배열이 주어진다. 인접한 두 집을 한꺼번에 훔치면 경보가 작동해 잡혀간다. 잡혀가지 않고 최대로 많이 훔칠수 있는 금액은? (인접한 집은 배열의 바로 다음요소라는 의미)

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.

https://leetcode.com/problems/house-robber/

해결 DP - bottom up - O(N^2)

두칸 이전 값부터 0번째까지 값중에 가장 큰값 + 현재 집 금액 을 더하는걸 반복하면 된다. 점화식을 아래와 같이 세워봤다.
초기값은 f(0) = nums[0], f(1) = nums[1]
f(n) = max(f(n-2) ~ f(0)) + nums(n)

뭔가 비효율적이다. DP라고 하더라도 시간복잡도가 O(N^2)이 되기 때문... (그런데도 채점 결과 100% faster가 나온건 의문)

int rob(int* nums, int numsSize){
    if (numsSize == 1) return nums[0];
    int *money = (int *)calloc(numsSize, sizeof(int));
    money[0] = nums[0];
    money[1] = nums[1];
    int max_money = money[0] > money[1] ? money[0]: money[1];
    
    for (int i = 2; i < numsSize; i++) {
        int prev_max = 0;
        for (int j = i - 2; j >= 0; j--) {
            if (money[j] > prev_max)
                prev_max = money[j];
        }
        money[i] = prev_max + nums[i];
        if (money[i] > max_money)
            max_money = money[i];
    }
    return max_money;
}

해결 DP 점화식 개선

Discuss 중에 추천 글 -> How to approach most of DP problems.
DP문제 풀이의 정석임. 반드시 또 읽기!

This particular problem and most of others can be approached using the following sequence:

Find recursive relation
Recursive (top-down)
Recursive + memo (top-down)
Iterative + memo (bottom-up)
Iterative + N variables (bottom-up)

if a problem is asking for the maximum/minimum/longest/shortest of something, the number of ways to do something, or if it is possible to reach a certain point, it is probably greedy or DP.

이 글을 읽고 개선된 점화식을 알게됐다. 강도가 현재 집 [i]에서 선택 할수 있는 행위는 두가지다.

• 1) 훔친다
• 2) 안훔친다

1)의 경우, 총 훔친 금액은 [i - 2] 까지 훔친 금액 + [i]에서 훔친 금액일것이고. 2)의경우는 [i-1] 까지 훔친 금액일 것이다. 이 두가지 중 더 큰값을 현재집의 총 훔친 금액으로 업데이트 하면 될것이다. 따라서 점화식은 다음과 같다.

f(i) = max(f(i-2) + curr_money,  f(i - 1))

그리고 문제에서 요구하는것이 마지막 집(i == n)에 도착할때 최대값이 아니라, 모든 경우의 수중 가장 큰 값으로 주어져서 점화식에서 마지막 값 f(n)을 구하는게 맞는건지 조금 햇갈렸는데. 그냥 점화식에서 f(n) 을 구하면 그게 최대값이된다. 최대값이 마지막까지 계속해서 누적되었기 때문이다.

풀이 1: DP top-down

memoization을 안해서 콜스택이 많이 쌓였을것, 당연히 Memory Limit Exceeded 발생!

class Solution {
private:
    int rob_func(vector<int> nums, int idx) {
        if (idx < 0)
            return 0;
        if (idx == 0)
            return nums[0];
        
        return std::max(rob_func(nums, idx - 2) + nums[idx], rob_func(nums, idx - 1));
    }
public:
    int rob(vector<int>& nums) {
        return rob_func(nums, nums.size() - 1);
    }
};

풀이 2: DP top-down + Memoization (배열) - O(N)

만약 memset(mem, 0, sizeof(int) * 101); memoization 초기 배열값들을 0으로 초기화 하면 TLE발생! -1로 초기화하면 PASS 왜?

class Solution {
private:
    int mem[101];
    int rob_func(vector<int> nums, int idx) {
        /* base case */
        if (idx < 0)
            return 0;
        if (idx == 0)
            return nums[0];
        
        /* memoization */
        if (mem[idx] != -1)
            return mem[idx];
        
        /* recursion */
        mem[idx] = std::max(rob_func(nums, idx - 2) + nums[idx], rob_func(nums, idx - 1));
        return mem[idx];
    }
public:
    int rob(vector<int>& nums) {
        memset(mem, -1, sizeof(int) * 101);
        return rob_func(nums, nums.size() - 1);
    }
};

풀이 2: DP top-down + Memoization (vector) - O(N)

vector 사용, 배열보다는 조금 느림.

class Solution {
private:
    int rob_func(vector<int> nums, int idx, vector<int> &mem) {
        /* base case */
        if (idx < 0)
            return 0;
        if (idx == 0)
            return nums[0];
        
        /* memoization */
        if (mem[idx] != -1)
            return mem[idx];
        
        /* recursion */
        mem[idx] = std::max(rob_func(nums, idx - 2, mem) + nums[idx], rob_func(nums, idx - 1, mem));
        return mem[idx];
    }
public:
    int rob(vector<int>& nums) {
        vector<int> mem(nums.size(), -1);
        return rob_func(nums, nums.size() - 1, mem);
    }
};

풀이 3: DP bottom-up - O(N)

마지막으로 bottom-up 풀이. 모든 DP문제는 top-down/bottom-up 둘다 해결 가능.

class Solution {
private:
    int mem[101];
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        memset(mem, -1, sizeof(int) * 101);
        mem[0] = nums[0];
        mem[1] = std::max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++)
            mem[i] = std::max(mem[i - 2] + nums[i], mem[i - 1]);
        return mem[nums.size() - 1];
    }
};

230121 다시 풀어봄

오래전에 풀어본 문제였음에도 불구하고, 빠르게 코딩하고 해결할 수 있었다. cur위치에서 도둑이 할수 있는 일이 훔치거나 안훔치는것 둘중하나 (이중에서 큰값 찾기)라는 해결방법이 기억이 나서 바로 풀 수 있었음.
Runtime: 0 ms, faster than 100.00%

class Solution {
public:
    vector<int> mem;
    int max_rob(vector<int> nums, int cur) {
        if (cur < 0)
            return 0;
        if (mem[cur] != -1)
            return mem[cur];
        
        mem[cur] = std::max(max_rob(nums, cur - 1), max_rob(nums, cur - 2) + nums[cur]);
        return mem[cur];
    }
    int rob(vector<int>& nums) {
        mem = vector<int>(nums.size(), -1);
        return max_rob(nums, nums.size() - 1);
    }
};