354.俄罗斯套娃信封问题

链接：354.俄罗斯套娃信封问题
难度：Hard
标签：数组、二分查找、动态规划、排序
简介：请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

题解 1 - typescript

• 编辑时间：2021-03-04
• 执行用时：444ms
• 内存消耗：42.2MB
• 编程语言：typescript
• 解法介绍：动态规划。

function maxEnvelopes(envelopes: number[][]): number {
  const len = envelopes.length;
  if (len === 0) return 0;
  envelopes.sort(([w1], [w2]) => w1 - w2);
  const dp: number[] = [1];
  for (let i = 1; i < len; i++) {
    const [w, h] = envelopes[i];
    let max = 1;
    for (let j = 0; j < i; j++) {
      const envelope = envelopes[j];
      if (w > envelope[0] && h > envelope[1]) max = Math.max(dp[j] + 1, max);
    }
    dp[i] = max;
  }
  return Math.max(...dp);
}