【每日算法】详解为何能从 LCS 问题转化为 LIS 问题,以及 LIS 贪心解的正确性证明 |Python 主题月

简介: 【每日算法】详解为何能从 LCS 问题转化为 LIS 问题,以及 LIS 贪心解的正确性证明 |Python 主题月

网络异常,图片无法展示
|


题目描述



这是 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 的子序列。
复制代码


示例 2:


输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出:3
复制代码


提示:


  • 1 <= target.length, arr.length <= 10^5105
  • 1 <= target[i], arr[i] <= 10^9109
  • target 不包含任何重复元素。


基本分析



为了方便,我们令 targettarget 长度为 nnarrarr 长度为 mmtargettargetarrarr 的最长公共子序列长度为 maxmax,不难发现最终答案为 n - maxnmax


因此从题面来说,这是一道最长公共子序列问题(LCS)。


但朴素求解 LCS 问题复杂度为 O(n * m)O(nm),使用状态定义「f[i][j]f[i][j] 为考虑 a 数组的前 ii 个元素和 b 数组的前 jj 个元素的最长公共子序列长度为多少」进行求解。


而本题的数据范围为 10^5105,使用朴素求解 LCS 的做法必然超时。


一个很显眼的切入点是 targettarget 数组元素各不相同,当 LCS 问题增加某些条件限制之后,会存在一些很有趣的性质。


其中一个经典的性质就是:当其中一个数组元素各不相同时,最长公共子序列问题(LCS)可以转换为最长上升子序列问题(LIS)进行求解。同时最长上升子序列问题(LIS)存在使用「维护单调序列 + 二分」的贪心解法,复杂度为

O(n\log{n})O(nlogn)


因此本题可以通过「抽象成 LCS 问题」->「利用 targettarget 数组元素各不相同,转换为 LIS 问题」->「使用 LIS 的贪心解法」,做到 O(n\log{n})O(nlogn) 的复杂度。


基本方向确定后,我们证明一下第 22 步和第 33 步的合理性与正确性。


证明



1. 为何其中一个数组元素各不相同,LCS 问题可以转换为 LIS 问题?


本质是利用「当其中一个数组元素各不相同时,这时候每一个“公共子序列”都对应一个不重复元素数组的下标数组“上升子序列”,反之亦然」。


我们可以使用题目给定的两个数组(targettargetarrarr)理解上面的话。


由于 targettarget 元素各不相同,那么首先 targettarget 元素和其对应下标,具有唯一的映射关系。


然后我们可以将重点放在两者的公共元素上(忽略非公共元素),每一个“公共子序列”自然对应了一个下标数组“上升子序列”,反之亦然


注意:下图只画出了两个数组的某个片段,不要错误理解为两数组等长。


网络异常,图片无法展示
|


如果存在某个“公共子序列”,根据“子序列”的定义,那么对应下标序列必然递增,也就是对应了一个“上升子序列”。


反过来,对于下标数组的某个“上升子序列”,首先意味着元素在 targettarget 出现过,并且出现顺序递增,符合“公共子序列”定义,即对应了一个“公共子序列”。


至此,我们将原问题 LCS 转换为了 LIS 问题。


2. 贪心求解 LIS 问题的正确性证明?


朴素的 LIS 问题求解,我们需要定义一个 f[i]f[i] 数组代表以 nums[i]nums[i] 为结尾的最长上升子序列的长度为多少。


对于某个 f[i]f[i] 而言,我们需要往回检查 [0, i - 1][0,i1] 区间内,所有可以将 nums[i]nums[i] 接到后面的位置 jj,在所有的 f[j] + 1f[j]+1 中取最大值更新 f[i]f[i]。因此朴素的 LIS 问题复杂度是 O(n^2)O(n2) 的。


LIS 的贪心解法则是维护一个额外 gg 数组,g[len] = xg[len]=x 代表上升子序列长度为 lenlen 的上升子序列的「最小结尾元素」为 xx


整理一下,我们总共有两个数组:


  • ff 动规数组:与朴素 LIS 解法的动规数组含义一致。f[i]f[i] 代表以 nums[i]nums[i] 为结尾的上升子序列的最大长度;
  • gg 贪心数组:g[len] = xg[len]=x 代表上升子序列长度为 lenlen 的上升子序列的「最小结尾元素」为 xx


由于我们计算 f[i]f[i] 时,需要找到满足 nums[j] < nums[i]nums[j]<nums[i],同时取得最大 f[j]f[j] 的位置 jj


我们期望通过 gg 数组代替线性遍历。


显然,如果 gg 数组具有「单调递增」特性的话,我们可以通过「二分」找到符合 g[idx] < nums[i]g[idx]<nums[i] 分割点 idxidx(下标最大),即利用 O(\log{n})O(logn) 复杂度找到最佳转移位置。


我们可以很容易 通过反证法结合 gg 数组的定义来证明 gg 数组具有「单调递增」特性。


假设存在某个位置 iijj,且 i < ji<j,不满足「单调递增」,即如下两种可能:


  • g[i] = g[j] = xg[i]=g[j]=x:这意味着某个值 xx 既能作为长度 ii 的上升子序列的最后一位,也能作为长度为 jj 的上升子序列的最后一位。 根据我们对 gg 数组的定义,g[i] = xg[i]=x 意味在所有长度为 ii 上升子序列中「最小结尾元素」为 xx,但同时由于 g[j] = xg[j]=x,而且「上升子序列」必然是「严格单调」,因此我们可以通过删除长度为 jj 的子序列后面的元素(调整出一个长度为 ii 的子序列)来找到一个比 g[i]g[i] 小的合法值。 也就是我们找到了一个长度为 ii 的上升子序列,且最后一位元素必然严格小于 xx。因此 g[i] = g[j] = xg[i]=g[j]=x 恒不成立;
  • g[i] > g[j] = xg[i]>g[j]=x:同理,如果存在一个长度为 jj 的合法上升子序列的「最小结尾元素」为 xx 的话,那么必然能够找到一个比 xx 小的值来更新 g[i]g[i]。即 g[i] > g[j]g[i]>g[j] 恒不成立。


根据全序关系,在证明 g[i] = g[j]g[i]=g[j]g[i] > g[j]g[i]>g[j] 恒不成立后,可得 g[i] < g[j]g[i]<g[j] 恒成立。


至此,我们证明了 gg 数组具有单调性,从而证明了每一个 f[i]f[i] 均与朴素 LIS 解法得到的值相同,即贪心解是正确的。


动态规划 + 贪心 + 二分



根据「基本分析 & 证明」,通过维护一个贪心数组 gg,来更新动规数组 ff,在求得「最长上升子序列」长度之后,利用「“公共子序列”和“上升子序列”」的一一对应关系,可以得出“最长公共子序列”长度,从而求解出答案。


Java 代码:


class Solution {
    public int minOperations(int[] t, int[] arr) {
        int n = t.length, m = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(t[i], i);
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int x = arr[i];
            if (map.containsKey(x)) list.add(map.get(x));
        }
        int len = list.size();
        int[] f = new int[len], g = new int[len + 1];
        Arrays.fill(g, Integer.MAX_VALUE);
        int max = 0;
        for (int i = 0; i < len; i++) {
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (g[mid] < list.get(i)) l = mid;
                else r = mid - 1;
            }
            int clen = r + 1;
            f[i] = clen;
            g[clen] = Math.min(g[clen], list.get(i));
            max = Math.max(max, clen);
        }
        return n - max;
    }
}
复制代码


Python 3 代码:


class Solution:
    def minOperations(self, t: List[int], arr: List[int]) -> int:
        n, m = len(t), len(arr)
        map = {num:i for i,num in enumerate(t)}
        lt = []
        for i in range(m):
            x = arr[i]
            if x in map:
                lt.append(map[x])
        length = len(lt)
        f, g = [0] * length, [inf] * (length + 1)
        maximum = 0
        for i in range(length):
            l, r = 0, length
            while l < r:
                mid = l + r + 1 >> 1
                if g[mid] < lt[i]:
                    l = mid
                else:
                    r = mid - 1
            clen = r + 1
            f[i] = clen
            g[clen] = min(g[clen], lt[i])
            maximum = max(maximum, clen)
        return n - maximum
复制代码


  • 时间复杂度:通过 O(n)O(n) 复杂度得到 targettarget 的下标映射关系;通过 O(m)O(m) 复杂度得到映射数组 listlist;贪心求解 LIS 的复杂度为 O(m\log{m})O(mlogm)。整体复杂度为 O(n + m\log{m})O(n+mlogm)
  • 空间复杂度:O(n + m)O(n+m)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1713 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
1月前
|
机器学习/深度学习 算法 TensorFlow
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现用户上传一张动物图片,识别其名称。
73 1
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
|
11天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
18 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
1月前
|
机器学习/深度学习 人工智能 算法
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
植物病害识别系统。本系统使用Python作为主要编程语言,通过收集水稻常见的四种叶片病害图片('细菌性叶枯病', '稻瘟病', '褐斑病', '稻瘟条纹病毒病')作为后面模型训练用到的数据集。然后使用TensorFlow搭建卷积神经网络算法模型,并进行多轮迭代训练,最后得到一个识别精度较高的算法模型,然后将其保存为h5格式的本地模型文件。再使用Django搭建Web网页平台操作界面,实现用户上传一张测试图片识别其名称。
96 22
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
|
1月前
|
机器学习/深度学习 人工智能 算法
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作界面,实现用户上传一张鸟类图像,识别其名称。
86 12
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
|
8天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
22 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
9天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
37 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
74 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
1月前
|
机器学习/深度学习 人工智能 算法
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
文本分类识别系统。本系统使用Python作为主要开发语言,首先收集了10种中文文本数据集("体育类", "财经类", "房产类", "家居类", "教育类", "科技类", "时尚类", "时政类", "游戏类", "娱乐类"),然后基于TensorFlow搭建CNN卷积神经网络算法模型。通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型,并保存为本地的h5格式。然后使用Django开发Web网页端操作界面,实现用户上传一段文本识别其所属的类别。
70 1
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
16天前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
34 1
|
16天前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
13 1