资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

利用动态规划解决最长增长子序列问题

创作时间:

作者:

@小白创作中心

利用动态规划解决最长增长子序列问题

引用

CSDN

https://blog.csdn.net/qq_44753451/article/details/109149799

一、题目及概念

1、题目描述

给定一个序列，找出其中最长的增长子序列（Longest Increasing Subsequence，简称LIS）。增长子序列是指在原序列中挑选出一些元素，保持原有的先后顺序，且这些元素是严格递增的。

2、子序列

子序列是指从给定序列中挑选出一些元素，保持原有的先后顺序。例如，给定序列A=[1, 2, 3, 4, 5]，序列A1=[1, 3, 5]和A2=[1, 2, 3]都是A的子序列，但序列B=[1, 3, 2]不是，因为它打破了元素原来的先后顺序。

3、增长（或上升）子序列

增长子序列是指子序列中的元素是严格递增的。例如，序列A=[4, 5, 1, 2, 3]中，序列A1=[1, 2, 3]是增长子序列，而序列A2=[4, 1, 3]不是，因为4>1破坏了增长的结构。

4、最长增长子序列

最长增长子序列是指在所有增长子序列中长度最长的那个。例如，序列A=[4, 5, 1, 2, 3]中，序列A1=[1, 2, 3]是最长增长子序列，而序列A2=[4, 5]不是，因为A1的长度大于A2。

二、分析并解决题目

1、寻求解决问题的方法

对于这种类型的题目，使用枚举法是不可行的，因为其时间复杂度会达到指数级。例如，使用最简单的枚举方法，所有可能的序列共有2^n个，即使不考虑其他操作所需的开销，它的时间复杂度也是指数级的。因此，这里采用动态规划的思想来解决这个问题。

动态规划的基本思想是将一个问题划分成一个个子问题，通过寻求子问题的最优解来解决整个问题。与分治法不同的是，当子问题不是相互独立时，动态规划会额外开辟一块空间来记录每个子问题的解，避免重复计算。

2、构建动态规划的模型

（1）分析优化解的结构

假设有一个序列[a, b, c, d, e, f, g]，已知序列[a, b, c, d, e, f]的最长增长子序列（记为最优解），要获取[a, b, c, d, e, f, g]的最优解，只需知道序列[a, b, c, d, e, f]中最大的元素m，将其与g比较，如果m<=g，就将g放在最优解的后面，否则就不加。依次类推，可以得到整个序列的最优解。

因此，该问题的优化子结构包括子序列的最优解以及子序列最优解中元素的最大值。

（2）构造状态转换方程

使用二维数组s[i][j]=m来存储子问题的最优解，其中：

i（即行）代表最优解的长度
j（即列）代表以a[j]结尾的子序列
m是最优解中最大的元素

状态方程可以表示为：

s[i][j] = max(s[i-1][k]) + a[j]，其中k < j且a[k] < a[j]

边界条件为：

s[1][j] = a[j]，即长度为1的子序列的最优解就是序列本身

（3）优化解的构建过程

以序列a[5]=[4, 5, 1, 2, 3]为例，构造s[i][j]：

其中，j表示a[]的下标，a[j]表示对应的元素的值；i表示最长增长子序列的长度。

从最左上角开始计算，因为以某个元素为结尾的子序列长度只能为1，所以第一行的值是a[j]。然后从第二行与对角线的交点开始填充第二行的数据，依次类推，直到计算出整个s[i][j]。

最终发现，深度最大的是以a[5]为结尾的最长增长子序列，即我们要求的解，为3。

3、存储结构的优化

（1）优化存储结构

可以只记录每一行的最小值，代表长度为i的所有增长子序列中最大元素中的最小值。使用一个可变长度的一维数组s[i]来表示，以及top代表可变长度数组的尾部下标。

（2）思路

最开始top是-1，代表可变长度的数组最开始是0。从左到右遍历a[]，当a[i]大于等于s[top]的时候，s[]长度加一，即top+1，然后将使s[top]=a[i]；当a[i]小于s[top]的时候，向左遍历s[]，找到s[m]与s[m+1]，使s[m]<=a[i]<s[m+1]，然后将s[m+1]替换成a[i]，即s[m+1]=a[i]。

（3）状态转换方程

略

（4）举例

对于序列a[5]=[4, 5, 1, 2, 3]：

从左到右开始遍历，当i=0时，s[0]=4
继续遍历，当i=1时，s[1]=5
继续遍历，当i=2时，s[1]=1
继续遍历，当i=3时，s[2]=2
继续遍历，当i=4时，s[3]=3

遍历结束后发现s[]最终的长度为3，所以最长增长子序列的长度是3。

4、记录最长增长子序列

（1）思路

设定p[j]，记录在优化解中a[j]的上一个元素m，而m在s[i]中的体现就是：当s[x]=a[j]时，p[j]=s[x-1]。

（2）举例

以序列a[5]=[4, 5, 1, 2, 3]为例：

初始化存储结构
遍历序列，更新s[]和p[]
最终结果图

得到最长增长子序列的长度是s.length=3，具体的最长增长子序列通过s[]记录的最后一个元素查p[]获得。

5、优化后的时间空间复杂度分析

空间复杂度是O(n)
时间复杂度暂定O(nlogn)

三、算法实现

1、C语言实现

为了简化判断量，对存储结构进行如下修改：

在a[]、s[]、p[]三个数组前都加一个0
使s[]和p[]中存对应元素的下标而不是对应的值

以下是具体的C语言代码实现：

#include<stdio.h>
#define LENGTH 6  // 序列长度
#define START 0
//int t[LENGTH] = {4, 5, 1, 2, 3};
int t[LENGTH] = {2, 3, 1, 4, 5, 4};  // 要求解问题的序列，可以换成自己输入
int max[LENGTH + 1];  // 记录所有长度的所有增长子序列中最大元素中的最小值，即上面讲的s[]
int pre[LENGTH + 1];  // 记录每个元素前一个元素的数组，即上面讲的p[]
int top = 0;  // max[]的尾端下标
int a[LENGTH + 1];  // t[]最开始填一个0
int main()
{
    init(pre);  // 初始化记录前一个元素的数组，最前面加个0
    init(max);  // 初始化记录每个长度的最优解最大值的数组，最前面加个0
    initArr(a);  // 初始化要求解问题的序列
    // 构建max[]以及pre[]
    for(int i = 1; i < LENGTH + 1; i++){
        if(a[i] >= a[max[top]]){
            pre[i] = max[top];
            top++;
            max[top] = i;
        } else {
            for(int j = top - 1; j >= 0; j--){
                if(a[i] >= a[max[j]]){
                    pre[i] = max[j];
                    max[j + 1] = i;
                    break;
                }
            }
        }
    }
    printf("max length: %d\n", top);
    printf("seq: ");
    printSeq(max[top]);  // 打印出求得的序列
    return 0;
}
// 初始化 max[] 和 pre[]，在最前面加个0
void init(int *a){
    for(int i = 0; i < LENGTH + 1; i++){
        *(a + i) = START;
    }
}
// 初始化输入数组，在最前面加个0
void initArr(int *a){
    *a = START;
    for(int i = 1; i < LENGTH + 1; i++){
        *(a + i) = t[i - 1];
    }
    return a;
}
// 递归打印最优解元素
void printSeq(int i){
    if(pre[i] == START){
        printf("%d ", a[i]);
        return;
    }
    printSeq(pre[i]);
    printf("%d ", a[i]);
}

序列[2, 3, 1, 4, 5, 4]运行结果如下：