354. Russian Doll Envelopes

week11

难度：Hard

题目链接

题目描述

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]).

题目分析

  再来一道动态规划的题目，本题是一道变形的最长子串题目，讲的是俄罗斯套娃那种排序，N个信封给出高和宽，若一个信封的高和宽都大于另一个信封，则可以装进去，目标求最长的序列。

解题思路

  这是一道比较常见的动态规划问题，记录每一个信封的最大装载数量，若有信封能装进该信封，那么比较装载数量，然后逐步找到最大装载数量的信封即可。

  将信封从小到大排序，宽度从小到大，宽度相同则高度从小到大，对后面的信封都要遍历前面的信封，看是否能装进去，然后更新dp，每次都比较下信封的最大装载量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
  public:
    int maxEnvelopes(vector<pair<int, int>> &envelopes)
    {
        vector<int> dp(envelopes.size(), 1);
        pair<int, int> temp;
        sort(envelopes.begin(), envelopes.end());
        int maxnum = 0;
        for (int i = 0; i < envelopes.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (envelopes[i].first > envelopes[j].first &&
                    envelopes[i].second > envelopes[j].second)
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxnum = max(maxnum, dp[i]);
        }
        return maxnum;
    }
};

结果反思

测试
测试

  从结果看来这种做法算是中规中矩，就是不断地去遍历，对信封的装载数量进行不断更新，最后达到收敛，就像Bellman-Ford算法一样不断更新，而且这个好像更加慢。。

目前最佳解法

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
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
    if (p1.first < p2.first) { return true; }
    else if (p1.first == p2.first) { return p1.second > p2.second; }
    return false;
}

bool cmp2(const pair<int, int> &p1, const pair<int, int> &p2) {
    return p1.second < p2.second;
}

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        vector<pair<int, int>> dp;
        sort(envelopes.begin(), envelopes.end(), cmp);
        for (const pair<int, int> &p : envelopes) {
            auto iter = lower_bound(dp.begin(), dp.end(), p, cmp2);
            if (iter == dp.end()) {
                dp.push_back(p);
            } else {
                dp[iter - dp.begin()] = p;
            }
        }
        return dp.size();
    }
};

代码分析

  第二种解法，这个似乎是现在最多且很快的解法，和求最长递增子串的长度相类似，运用了其中的思想，也就是贪心和二分的想法，先对宽度从小到大进行排序，这样能保证后面的信封能装进前面的信封，然后对高度进行最长递增子串寻找最长，这样就能得到最长，也许会出现宽度相同的情况，但是这也说明了最长递增子串这个问题的想法，得到的解并不会是正确的解，但是长度是相同的，对较大的进行置换成小的使得它能够得到更大的潜力去递增，这就是贪心的策略，在贪心的同时并没有改变其中的长度，很精妙。。。

总结

  这个题目说明了动态规划有时候并不会是最简单的，但也是比较快的了，动态规划能够避免许多小问题的重复求解，在求得对应的序列比递归有很大的优势，在一些问题归纳若子问题的规模仍很大，那么动态规划比递归好很多。第二种的贪心二分算法是在题目只要求得长度，这样贪心算法就能最速得到长度，但是始终得不到序列。要得到指定序列还是需要动态规划。可以说是套着dp的皮，实则是贪心策略。