力扣之最长上升子序列 2022-02-28~03-06
发布网友
发布时间：2023-03-12 12:19
共1个回答
热心网友
时间：2023-05-14 12:50
注意dp的定义以及为什么要排序
定义 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度， 注意 必须被选取。
同上，先按照第一维进行排序，然后在第二维寻找LIS
排序的意义 ：通过对第一维进行排序，在动态规划求 的过程中，使得所有可能满足的前面的嵌套都已经求完， 不存在后面的信封能放在前面的任何一个信封里面 ，例如 [[5,4],[6,4],[6,7],[2,3]] ，最后一个信封能放在前面的信封里
和上面一模一样，复杂度也是
排序也 只用排第一维 ，因为 排序的意义在于遍历后面的箱子时确保前面的结果不会再改变了
