DFS or topological sorting
The solution I propose may not be as efficient as many other solutions posted. But I find topological sorting is very intuitive here and is quite interesting. C
The solution I propose may not be as efficient as many other solutions posted. But I find topological sorting is very intuitive here and is quite interesting. Consider each doll is a node in a graph. Two nodes are connected if one can contain another. It is easy to come up with a O(n^2) solution with DFS:\n\n```\nclass Solution {\n    // Topological sorting\n    public int maxEnvelopes(int[][] envelopes) {\n        int[] visited = new int[envelopes.length]; // we need to memorize the longest path of each node.\n        int max = 0;\n        for (int i=0; i<envelopes.length; i++) {\n            max = Math.max(max, dfs(i, envelopes, visited));\n        }\n        return max;\n    }\n    \n    private int dfs(int cur, int[][] envelopes, int[] visited) {\n        if (visited[cur] > 0) {\n            return visited[cur];\n        }\n        \n        int max = 1;\n        for (int i=0; i<envelopes.length; i++) {\n            if (envelopes[i][0] < envelopes[cur][0] && envelopes[i][1] < envelopes[cur][1]) {\n                max = Math.max(max, dfs(i, envelopes, visited) + 1);\n            }\n        }\n        visited[cur] = max;\n        \n        return max;\n    }\n}\n```
[]