LeetCode-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?不包含任何重复元素。
通过次数1,445提交次数3,140

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence

解析：

ans=len(A)-LCS(A,B)，LCS：最长公共子序列

方法一：DP法

• 定义：dp[i][j] = A[:i] 和B[:j]的LCS
• 初始化：dp[*][*] = 0
• 公式：dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]+A[i]==B[j])
• 结果：dp[m][n]
• 复杂度：O(mn)
• 通过情况：63?/?82?个通过测试用例

def minOperations1(target, arr):
    m, n = len(target), len(arr)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            dp[i][j] = max([dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + int(target[i-1] == arr[j-1])])
    return len(target) - dp[m][n]

方法二（优化）：

注意题中的提示：target?不包含任何重复元素。

target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]

将target 转换成序号：[0,1,2,3,4,5]

arr相应数字也进行替换：[1,0,5,4,2,0,3]，没有的删除

由于target序号一定是递增序列，因此本题可以转换成寻找-最长单调递增子序列，参见：300. 最长递增子序列

复杂度：O(n)

def minOperations2(target, arr):
    def LIS(A) -> int:
        dp = []
        for x in A:
            if not dp or x > dp[-1]:
                dp.append(x)
            else:
                dp[bisect_left(dp, x)] = x
        return len(dp)

    map_set = {x: i for i, x in enumerate(target)}
    new_arr = [map_set.get(x) for x in arr if x in map_set]
    return len(target) - LIS(new_arr)

?