Halo

A magic place for coding

0%

LeetCode 解题报告(331) -- 354. Russian Doll Envelopes

Problem

You are given a 2D array of integers envelopes where envelopes [i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

1
2
3
Input: envelopes = [[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]).

Example 2:

1
2
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

  • 1 <= envelopes.length <= 5000
  • envelopes [i].length == 2
  • 1 <= wi, hi <= 104

Analysis

   题目是俄罗斯套娃,要求长和宽都必须严格小于才能套进去。很自然的做法是先排序,按照长度从小到大排序,如果长相等,再按照宽来排序。因为我们要找到的套得最多的一种组合,这就有点像子序列问题的,所以用贪心算法是肯定不行的,考虑的方向往 dp 上靠。

   定义 dp [i] 为选择了第 i 个娃娃所能构成的最大的数量。我们从小到大来遍历,对于每个位置 i,我们向前遍历 [0, i-1],只要满足套娃的要求,就更新状态方程,找到最大的数量。


Solution

   注意初始化 dp 数组的时候初始值是 1,因为单独一个套娃的长度是 1,不是 0。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort (envelopes.begin (), envelopes.end (), [](vector<int> &A, vector<int> &B) {
if (A [0] < B [0]) {
return true;
} else if (A [0] == B [0]) {
return A [1] < B [1];
}
return false;
});
int size = envelopes.size ();
vector<int> dp(size, 1);

int result = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < i; j++) {
if (envelopes [i][0] > envelopes [j][0] && envelopes [i][1] > envelopes [j][1]) {
dp [i] = max (dp [i], dp [j] + 1);
}
}
result = max (result, dp [i]);
}
return result;
}
};

Summary

   这是一道比较简单的 dp 题目,其本质和字符串子序列题目一样。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels