354. Russian Doll Envelopes!

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        //sort the array by the width in ascending order, convert the probelm to LIS
        Arrays.sort(envelopes, (a, b)->a[0]-b[0]);
        // j in the range of [0, i-1];
        // dp[i] = max(1+dp[j],1);
        int len = envelopes.length;
        int[] memo = new int[len];
        int ans = 0;
        for(int i=0; i<len; i++){
            //min of memo[i] is 1;
            memo[i]=1;
            for(int j=0; j<i; j++){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    memo[i]=Math.max(memo[i], 1+memo[j]);
                }
            }
            ans = Math.max(ans, memo[i]);
        }
        return ans;
    }
}