每日算法如何将 LCS 问题巧妙转化为 LIS 问题，并证明 LIS 贪心解的合理性？

本文共计2759个文字，预计阅读时间需要12分钟。

题目描述：这是LeetCode上的题目，编号为1713，题目是得到子序列的最小操作次数。难度为中等。Tag： 最长公共子序列、最长上升子序列、贪心、二分。给你一个数组target，包含若。给你一个数组target，包含若。

题目描述

这是 LeetCode 上的 ​​1713. 得到子序列的最少操作次数​​ ，难度为 中等。

Tag : 「最长公共子序列」、「最长上升子序列」、「贪心」、「二分」

给你一个数组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 的子序列。