问题描述:
给定一个数组str=[5, 3, 4, 8, 6, 7,9],求出其最长递增子串:LongestIncreaseSub=[3,4,6,7,9]
解决思路:
解决最长子序列(Longest Increase Subset, LIS)问题,使用动态规划(Dynamic Programming,DP),之前说到动态规划的规划(Programming)是表格的意思,是对递归的一种优化,递归是不管需不需要都进行重新计算,其计算复杂度极高,动态规划用表格(数组)来存储其之前的状态,当进行下一步计算的时候直接调用不需要重新计算。那么问题来了,动态规划需要确定两个点:状态、状态转移方式[1]。在这里从另一个角度说一下动态规划:
已知问题规模为n的已知条件Y,求解一个未知解X。(我们用Yn表示“问题规模为n的已知条件”)
此时,如果把问题规模降到0,即已知Y0,可以得到Y0->X.
如果从Y0添加一个元素,得到Y1的变化过程。即Y0->Y1; 进而有Y1->Y2; Y2->Y3; …… ; Yi->Yi+1. 这就是严格的归纳推理,也就是数学归纳法;
对于Yi+1,只需要它的上一个状态Yi即可完成整个推理过程(而不需要更前序的状态)。我们将这一模型称为马尔科夫链(自然语言处理中经常使用)。对应的推理过程叫做“贪心法”。
然而,Yi与Yi+1往往不是互为充要条件,随着i的增加,有价值的前提信息越来越少,我们无法仅仅通过上一个状态得到下一个状态,因此可以采用如下方案:{Y1->Y2}; {Y1, Y2->Y3}; {Y1,Y2,Y3->Y4};……; {Y1,Y2,...,Yi}->Yi+1. 对于Yi+1需要前面的所有前序状态才能完成推理过程, 高阶马尔科夫链。也就是DP的另一个解释。
借用文献[2]中一个形象的图就是:
文献[3]中说动态规划就是一个基于有模型的强化学习方法。
回归到本文的问题,首先应当记录在有1,2,3,m,...n 个元素时各自的LIS;
然后在建立第m个元素时LIS时,需要考虑当前缀为1,2...,m时的递增长度,取其中最长的。
例如对于这个序列str=[5, 3, 4, 8, 6, 7,9],当考虑元素6的时候,其最长子序列为以4结尾的LIS,而4的LIS是以3结尾的LIS,如图所示:
所以其状态转移公式为:if(str[m]>str[preIndex]): LIS[m]=max{ LIS[preIndex]+1 }
此处需要使用两层for循环进行遍历,第一次表示当有index个数据时的最长子串,第二次表示当前缀为preIndex是的长度,然后判断是否更新。
python代码:
import copy
# 最长递增子串
str=[5, 3, 4, 8, 6, 7,9]
def find(str):
long=1
status = []
sub=[]
for index in range(len(str)): # 从第0个元素开始建立
status.append(1)
pre=0
for preIndex in range(index): # 从前面(第0个)元素中开始更新
if(str[preIndex]<=str[index] and status[preIndex]+1>status[index]):
# 如果当前元素小于元素,且更新后长度更长
status[index]=status[preIndex]+1
pre=preIndex
# 记录每一种状态下的子串
# print("pre",pre)# 记录的是上一个合适的子串的位置
if(status[index]>long):
long=status[index]
if(long==1):
sub.append([str[index]])
else:
new=copy.copy(sub[pre])
new.append(str[index])
sub.append(new)
# print(new)
print(str)
print(long)
print(status)
print(sub)
if __name__=="__main__":
find(str)
运行结果为:
其中,最后一行为在不同数据长度下的LIS记录。使用pre变量记录最长递增子串的前缀,当记录清所有前缀后,即可记录并打印出所有的子串。
参考文献:
[1] 0-1背包问题:动态规划 python 空间优化 https://blog.csdn.net/linweieran/article/details/100585052
[2] 六大算法之三:动态规划 https://blog.csdn.net/zw6161080123/article/details/80639932
[3] 动态规划(Dynamic Programming):基于有模型的强化学习方法 https://www.jianshu.com/p/f63d674b7688