Delete and Earn(Java)

이 문제도 내가 기억하기로는 군대를 막 전역하고 풀었던 문제다. 그때도 Memoization 방식으로 풀었지만 사실 그렇게 잘 이해는 못했다. 다시 문제를 도전하는 느낌으로 DP 테이블을 짜고 풀어봤는데 훨씬 이해가 잘되는 기분이다.

결론적으로 많이 헤맸고 못풀어서 답을 참고했다. 그리고 이 문제를 통해서 배운점이 몇가지 있다.

일단 이 문제는 하나의 숫자를 선택했을때 그 숫자보다 +1 혹은 -1인 모든 숫자는 지워진다. 그리고 이 과정을 전부 거친 후에 최고 값을 가지고 오면 된다.

난 HashMap 을 사용해서 total - num[i] +1 + num[i] -1 같이 단순하게 풀려고 했는데 테스트 케이스는 통과해도 다른것들이 통과 못했다. 왜? 겹치지 말아야하는 구간을 포함 시켰기 때문이다.

결국 DP 문제는 겹치는 구간을 어떻게 잘 처리하냐가 가장 중요한거같다.

그래서 다른 풀이 방식으로는 House Robber 을 풀었던 선택하냐 선택하지 않냐의 선택을 따라서 구간을 계속해서 공략해주었다. 먼저 루핑을 통해 같은 숫자를 가진 합을 더 해주었다.

이후에는 2부터 마지막 숫자까지 또 한번 루핑을 했는데 dp[i-1] 그리고 dp[i-2] + 현재 숫자의 선택을 했다.

dp[i-1]의 선택같은 경우 현재의 숫자를 선택하지 않는다의 결론이다. 바로 전까지의 구간을 선택한다 인데 이유로는 현재 숫자 - 1의 합은 선택할 수 없기 때문이다.

dp[i-2] + 현재숫자는 선택한다 의 결론이다. 현재숫자 -1이 아닌 구간은 전부 더할수 있기때문에 현재 숫자까지 선택한 합이랑 비교하면서 max 값을 구하면 끝난다!

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] dp = new int[10002];
        List<Integer> container = Arrays.stream(nums).boxed().toList(); 
        int lastNum = Collections.max(container); 
        for(int i = 0; i < nums.length; i++){
            dp[nums[i]] += nums[i];
        }

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

class Solution {
    int dp[10002]; 
public:
    int deleteAndEarn(vector<int>& nums) {
        int lastElement = *max_element(nums.begin(),nums.end()); 
        for(int i = 0; i < nums.size(); i++){
            dp[nums[i]] += nums[i]; 
        }
        
        for(int i = 2; i <= lastElement; i++){
            dp[i] = max(dp[i-1], dp[i-2] + dp[i]); 
        }

        return dp[lastElement]; 
    }
};