O(n^2) Time, O(n) Space, Java DP Solution With Simple Explanation, 426ms


  • 0

    Basic Idea:

    • Sort the original envelopes, fit in as many as possible.
    • dp[i] stands for the maximum number when put envelopes i into others
    • the initial value for dp[i] is 1
    • Transition: dp[i] = max(dp[j] for all possible envelope j which i can put in, j starts from i+1)+1
    public class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            int max = 1;
            int n = envelopes.length;
            if(n <= 1) return n;
            int[] dp = new int[n+1];
            Arrays.sort(envelopes, new java.util.Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return Integer.compare(a[0], b[0]);
                }
            });
            for(int i = 0; i < n; i++)dp[i] = 1;
            for(int i = n - 2; i >= 0; i--){
                int tmp = dp[i];
                boolean hasFit = false;
                for(int j = i+1; j < n; j++){
                    if( dp[j] >= tmp &&  isFit(envelopes[i][0],
                                               envelopes[j][0],
                                               envelopes[i][1],
                                               envelopes[j][1])){
                        tmp = dp[j];
                        hasFit = true;
                    }
                }
                if(hasFit)dp[i] = tmp+1;
                if(dp[i] > max) max = dp[i];
            }
            return max;
        }
        
        boolean isFit(int wi, int wj, int hi, int hj){
            if( wi < wj && hi < hj)return true;
            else return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.