UP-BOTTOM DP. Why TLE?


  • 0
    R
    public class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            HashMap<Integer,HashMap<Integer,Integer>> dp = new HashMap<Integer,HashMap<Integer,Integer>>();  
            Arrays.sort(envelopes,new Comparator<int[]>() {
                public int compare(int[] o1, int[] o2) {
                    return o1[0]-o2[0];
                }
            });
            
            int max = 1 ;
            for (int i=0; i< envelopes.length;i++) {
                max = Math.max(max, maxdp(dp,envelopes,envelopes[i][0],envelopes[i][1],i));
            }
            return max;
        }
        
        private int maxdp(HashMap<Integer,HashMap<Integer,Integer>> dp, int[][] envelopes, int width, int height, int idx) { 
            if (dp.containsKey(width) && dp.get(width).containsKey(height)) {
                return dp.get(width).get(height);
            }
            int max = 1;
            for (int i = 0; i<idx && envelopes[i][0]<width;i++) {
                if (envelopes[i][1]<height) {
                    max = Math.max(max,1+maxdp(dp,envelopes,envelopes[i][0], envelopes[i][1],i));
                }
            }
            HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
            if (dp.containsKey(width)) {
                temp = dp.get(width);
            }
            temp.put(height,max);
            dp.put(width, temp);
            return max;
        }
    

    I use the DP idea to solve this question. And before it I sort the envelopes. The running time is O(n^2). Why is it TLE?


Log in to reply
 

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