# 1713. 得到子序列的最少操作次数
### 题目地址(1713. 得到子序列的最少操作次数)
### 题目描述
```
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。
示例 1：
输入：target = [5,1,3], arr = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例 2：
输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出：3
提示：
1 <= target.length, arr.length <= 105
1 <= target[i], arr[i] <= 109
target 不包含任何重复元素。
```
### 前置知识
* 动态规划
* LIS
### 公司
* 暂无
### 思路
这道题属于最长上升子序列的换皮题。关于最长上升子序列可以参考我之前写的文章[穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)
具体的思路为：
1. 新建一个空的列表 B
2. 遍历 arr， 如果 arr 中的数字存在于 target 中，将其索引添加到列表 B 中
3. 求列表的最长上升子序列的长度（典型算法），这个长度实际上就是我们可以利用 arr 中的数所能组成的 **最长的** target 的子序列，换句话说，我们添加最少的数就可以构成 target。
4. 答案就是 target 的长度减去最长子序列的长度。
* 为了加快第 2 步的速度，可以建立 target 的反向索引方便能够在 $O(1)$ 时间根据 val 获取到索引。
* 由于这道题数据范围是 $10^5$，因此只能使用 $NlogN$ 的贪心才行。
> 关于为什么 10 ^ 5 就必须使用 $NlogN$ 甚至更优的算法我在[刷题技巧](https://lucifer.ren/blog/2020/12/21/shuati-silu3/)提过。更多复杂度速查可参考我的刷题插件，公众号《力扣加加》回复插件获取即可
### 关键点
* LIS
### 代码
```py
class Solution:
def minOperations(self, target: List[int], A: List[int]) -> int:
def LIS(A):
d = []
for a in A:
i = bisect.bisect_left(d, a)
if d and i < len(d):
d[i] = a
else:
d.append(a)
return len(d)
B = []
target = { t:i for i, t in enumerate(target)}
for a in A:
if a in target: B.append(target[a])
return len(target) - LIS(B)
```
**复杂度分析**
* 时间复杂度：$O(max(BlogB, A))$。
* 空间复杂度：由于 target 大小大于 B 的大小，因此空间复杂度为 $O(target)$。
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
