[LeetCode] Russian Doll Envelopes

문제설명

넓이와 높이가 다른 봉투가 많이 있다.
넓이와 높이모두 큰 봉투는 작은 봉투를 담을 수 있는데 최대로 많이 담을 수 있는 수를 구하여라!

풀이방법

전형적인 DP 문제라 생각했다.
Top -down 방식을 연습하고 있어서 그렇게 풀겠다.

코드

class Solution {
    int[] dp;
    
    public int maxEnvelopes(int[][] envelopes) {
        int[][] newEnvelopes = new int[envelopes.length+1][2];
        
        boolean[] visited = new boolean[newEnvelopes.length];
        dp = new int[visited.length];
        Arrays.fill(dp,-1);
        
        newEnvelopes[0][0]= Integer.MAX_VALUE;
        newEnvelopes[0][1]= Integer.MAX_VALUE;
        
        for(int i=1; i<newEnvelopes.length;i++)
            newEnvelopes[i] = envelopes[i-1];
        
        int ans = 0;
        ans = Math.max(ans, getRussianDoll(newEnvelopes,visited,0));
        
        return ans;
    }
    
    public int getRussianDoll(int[][] envelopes, boolean[] visited, int start){
        if(dp[start]!=-1) return dp[start];
        
        int ret = 0;
        
        for(int i=0; i<envelopes.length; i++){
            if(visited[i]) continue;
            if(envelopes[start][0]>envelopes[i][0]
              &&envelopes[start][1]>envelopes[i][1]){
                visited[i] = true;
                ret = Math.max(getRussianDoll(envelopes,visited,i)+1,ret);
                visited[i] = false;
            }
        }
        return dp[start]=ret;
    }
}

해결

봉투를 정렬해서 모든 봉투에 대해 조사를 하지 않으면 더 최적의 결과가 나올것!