# Question

Formatted question description: https://leetcode.ca/all/354.html

 354	Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h).

One envelope can fit into another if and only if:
both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

Example:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

@tag-dp


# Algorithm

Consider a situation [100,100],[200,200], [1,300],[2,400],[3,500]. If you only update x in p(x,y) every time, then the next three will be thrown away, and the maximum value is 2, while correct reulst should be 3.

First, we must sort all the envelopes from smallest to largest.

• First row according to the width from small to large,
• If the width is the same, then the height is smaller and then the front,

Then we start to traverse, for each envelope, we traverse all the envelopes before it,

• If the length and width of the current envelope are larger than those of the previous envelope, then we update the dp array by dp[i] = max(dp[i], dp[j] + 1).
• Then every time we traverse an envelope, we update the result

### Follow up of this question

If the envelope can be rotated. What is the longest sequence?

The answer is to enqueue <3,4>, then <4,3> also enqueue, and then find the longest sequence.

Java