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

• 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;
}
}
``````

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