354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。> 说明：不允许旋转信封。 示例：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3

解题思路1-动态规划

动态规划 最长递增子序列之信封嵌套问题

先对宽度w进行**升序排序，如果遇到w相同的情况，则按照高度h降序排序。之后把所有的h作为一个数组，在这个数组上计算 LIS **的长度就是答案。
image.png image.png
这个解法的关键在于，对于宽度w相同的数对，要对其高度h进行降序排序。因为两个宽度相同的信封不能相互包含的，而逆序排序保证在w相同的数对中最多只选取一个计入 LIS。

  1. class Solution {
  2. public:
  3.     int maxEnvelopes(vector<vector<int>>& envelopes) {
  4.         int n = envelopes.size();
  5.         sort(envelopes.begin(),envelopes.end(),cmp);
  6.         vector<int> height(n);
  7.         for (int i = 0;i < n;i++) height[i] = envelopes[i][1];
  8.         return lengthOfLIS(height);//返回按高度作为一个数组的最长递增子序列的长度
  9.     }
  11.     int lengthOfLIS(vector<int> nums) {
  12.         int n = nums.size();
  13.         vector<int>dp(n,1);
  14.         for (int i = 0;i < n;i++) {
  15.             for (int j = 0; j < i;j++) {
  16.                 if (nums[i] > nums[j])
  17.                     dp[i] = max(dp[i],dp[j] + 1);
  18.             }
  19.         }
  20.         int ans = 0;
  21.         for (int i = 0;i < n;i++) {
  22.             if (dp[i] > ans) ans = dp[i];
  23.         }
  24.         return ans;
  25.     }
  27.     static bool cmp(vector<int> a, vector<int> b)
  28.     {
  29.          if (a[0] != b[0]) return a[0] < b[0];//第一个参数按升序
  30.          else return a[1] > b[1];//第二个参数按降序
  31.     }
  32. };