第二章、动态规划算法(2.6.1-2.6.2.3)------单序列问题(上)

目录
2.6动态规划算法实现------单序列问题
2.6.1最长递增子序列问题
2.6.1.1问题
2.6.1.2确定动态规则(DP、状态转移方程)、初始值
2.6.1.3动态规划算法代码实现
2.6.2最长连续递增子序列问题
2.6.2.1问题
2.6.2.2确定动态规则(DP、状态转移方程)、初始值
2.6.2.3动态规划算法代码实现

2.6动态规划算法实现------单序列问题

2.6.1最长递增子序列问题

2.6.1.1问题

       最长递增子序列(longest increase subsequence，LIS)，给定序列A，求A中按顺序元素值递增的元素构成的最长子序列的长度，这个子序列称为序列A的最长递增子序列(longest increasing subsequence)，也称最长上升子序列。

       本题是在一个序列中找出最长递增子序列的长度。最长递增子序列也称最长单调递增子序列。从数学上讲，严格递增子序列按从左到右的顺序元素值是递增的，不包括元素值相等的情形，而递增子序列按从左到右的顺序元素值是不减的，也即增加或相等都可以。两者在求解比较中就是＜和≤的区别。在求解时可以不做严格区分。  

       计算机的序列是指序列的元素在代码中呈现出的顺序与内存存储顺序一致，在计算机中序列是可以通过索引来引用的。在python中字符串、列表、元组都是序列。

       子序列是保持原序列中的顺序，比如：’ea’是’eahjkf’的子序列，但’ae’不是它的子序列。本题是关于递增序列问题，这种序列一般是数字型的序列。比如：序列[1,4,5,2]，它的多个元素构成的递增子序列为 [1,4] 、[1,5] 、[4,5] 、[1,4,5]、[1,2]，它的最长递增子序列为[1,4,5]。

        下面不仅求最长递增子序列的长度，还求出最长递增子序列及其个数(数量)。

2.6.1.2确定动态规则(DP、状态转移方程)、初始值

(1)直接相关状态

        本题是找出单个序列中最长递增子序列(longest increasing subsequence)的长度，而前面我们讲述的实例是找出公共子序列问题，即在多个序列中找出公共子序列，这涉及到是否匹配，但本题是一个序列的单调性的判断，单调性也就是递增或递减的特点。本题是考虑递增的单调性，求最长递增子序列的长度。

       当前状态的最长递增子序列是由当前位置的元素与之前位置形成递增关系的元素组成，若不能形成递增关系，则与之前的这个状态的递增子序列没有关系，因而，我们需要把当前位置与之前位置进行判断是否存在递增关系，若存在，在原基础上求出这时当前状态对应的一种递增子序列的长度，并且保留这个值，以便它与当前位置与之前其他位置进行判断后所求的递增子序列的长度进行比较，并保留这种比较的最大的值，通过这种方式，最终获得了当前状态对应最长递增子序列的长度。可见，当前状态的直接相关状态与之前的所有状态是可能都有关的，但具体还需要在循环中判断，然后进行比较，最终得到当前状态的最长递增子序列的长度。

       不妨记A=[1,4,5,2,3]，我们考察元素2，它的递增子序列为[2]、[1,2]，通过长度比较可以确定最长递增子序列长度为2，元素2的递增子序列与自身和1有关。元素2与4、5都不能构成递增关系，因而元素2位置的状态值只与自身和元素1位置的状态值有关，与4或5位置的状态值无关，这个元素2位置自身状态值就是下面将讲到的初始值，即这里是元素2位置的初始值，在这里这个初始值就可以看作是[2]的长度，即为1。

       但元素4位置，它的递增子序列为[4]、[1,4]，通过长度比较可以确定最长递增子序列长度为2。元素5位置，它的递增子序列为[5]、[1,5]、[4,5]、[1,4,5]，通过长度比较可以确定最长递增子序列长度为3。

       我们再考察元素3，它的递增子序列为[3]、[1,3]、[1,2,3]，通过长度比较可以确定最长递增子序列长度为3。元素3与4、5都不能构成递增关系。

       上面分析中我们考虑自身单个元素作为递增子序列，这可以看作是一种特例，这种特例也就是下面讲到的初始值。

       由上面例子可以看到，当前状态前面的状态即使代表的最长递增子序列长度比较大，也不一定与当前状态组成递增关系，甚至有可能出现当前状态与之前的状态都没有递增关系。当前状态具体与之前哪些状态有直接关系需要判断确定，在这个判断过程中不断比较构成的递增子序列长度，保留最大的长度值，最终就可以确定当前状态的最长递增子序列长度。

       通过循环比较当前状态位置的元素与之前位置的元素来确定是否存在递增关系，进而判断确定当前状态与之前的状态是否存在关系，这种与当前状态存在递增关系的之前状态就是当前状态的直接相关状态。递增是推动状态转移的因素。

(2)当前状态值的确定

      状态与状态值是不能等同的，状态是一种定性的描述，状态值是问题所要求的一种定量的衡量。并不一定是所有的直接相关状态都参与确定当前状态值。当前状态值的唯一性确定还可能与状态转移的因素的作用、求解问题的要求、问题自身的规律特点有关。      

       由上面直接相关状态的分析可知，需要在循环中判断确定直接相关状态，而且当前状态的所有直接相关状态都参与长度比较，从而最终确定当前状态值。

       我们记状态i的值dp[i]为序列A的索引i位置的最长递增子序列长度，则dp[i]的值的确定与i之前的索引位置的状态值可能有关，但需要判断是否存在递增关系。不妨记j是i之前的索引，即j取值在0到i-1，且为整数，也即j在区间[0,i)取整数值。我们需要比较A[i] ≥A[j]，若该不等式成立，则A[j]与A[i]存在递增关系，状态j是当前状态i的一个直接相关状态，显然，由状态j转移到状态i，增加了一个元素，达到i状态为dp[j]+1值，由于j在区间[0, i)取值，我们需要找出所有符合A[i] ≥A[j]的dp[j]+1，并比较大小，最终得到最大的一个dp[j]+1即为状态i的值dp[i]。  

      上述这个计算过程在计算机中可以用j在区间[0,i)的循环判断A[i] ≥A[j]，判断为真则计算dp[i] = max(dp[i],dp[j] + 1)来求解。等式右边的dp[i]就是上一次比较保留的最大的值，等式左边的dp[i]是本次比较保留的最大的值，通过这种不断比较更新即可最终得到i状态的最长递增子序列长度。

       当A[i] <A[j]时，也就是两者没有递增关系，j状态到i状态没有状态转移关系。

(3)动态规则(DP、状态转移方程)

      上面的描述可以表示为下面的动态规则(DP、状态转移方程):

       通过上面状态转移方程，循环i，我们可以求得所有状态的最长递增子序列长度，最后在这些值中找出最大的一个值即是我们所求的值。

       本题也是用两层循环，外层循环是i，内层循环是j，外层循环i代表当前状态，j是当前状态i之前的状态（具体作用见上面的分析）， j在区间[0,i)里循环取值。在两层循环中，外层循环运行一个i，内层循环j遍历一遍。

(4)初始值

       初始状态值不一定由通用的状态转移方程计算得到，可以是人为规定的，但应符合动态规划的计算，使得计算机计算时获得初始值并符合问题的求解。

       本题是通过比较求最长递增子序列，我们可以不需要像前面求公共子序列一样额外增加空字符建立初始的匹配关系，本题只需要比较本序列的元素即可。本题的dp[i]初始值可以赋值为1，相当于各个元素作为一个元素的递增子序列时，其长度为1。而且一个元素即使与它之前位置的元素不构成递增关系，但可能与它之后的序列构成递增关系，这时相当于它是某个递增子序列长度的起始点，因而初始值为1是合理的，若初始值不赋1，这种情形就会出现计算错误。dp[i]初始值赋1也符合其他情形，因为由上面分析可知计算时实际是在不断比较更新，不影响计算结果。

       进一步讲，单个元素可以看作是一个特殊的递增子序列，可以看作是这个元素的初始状态，把单个元素看着是一个递增子序列，它的值就是1。

       本题没有像前面求公共子序列一样额外增加空字符的位置，dp的索引与A的索引是一致的。

2.6.1.3动态规划算法代码实现

       上面的分析及下面代码的实现可以结合下面图2-27来理解。浅红色方框的状态与前面浅蓝色方框的状态有递增关系，但在代码中是通过判断来确定是否存在递增关系。

图 2-27 最长递增子序列

       从上面图2-27中，我们可以看到，当前状态与前面位置的状态可能构成多个递增子序列，其中最长的就是当前状态的值，而且当前状态都含有当前位置一个元素构成的递增子序列，这个单个元素的子序列可以看作是当前位置的初始状态，其长度是1。

(1)完整代码

       下面程序代码是求解最长递增子序列问题，函数Longest_increase_subsequence_length ()采用动态规划求解最长递增子序列的长度，是按上述分析过程实现的，完全体现了我们上面对动态规划的论述，从代码中就能看到动态规划算法的思想，我们可以结合下面代码来理解动态规划算法在本问题中的应用。

       代码中函数find_LIS_dynamic()采用动态规划求解最长递增子序列。

#A为序列,比如:python中的字符串,列表等,这里用数字型的序列为例求最长递增子序列。
#最长递增子序列(最长上升子序列)长度。最长递增子序列。
import copy
def Longest_increase_subsequence_length(A):
    n= len(A)

    #生成一个一层列表,存放状态值。
    #下面直接赋值1,也是动态规划的初始值,相当于各个元素作为一个元素的递增子序列时,其长度为1。
    #初始值为1,相当于一个元素,下面循环中进行判断比较时,可能作为比较的基础。
    #比如:某个元素比它前面的元素小,但它后面的元素比它大,那么这个元素和它后面的元素构成的递增子序列时,
    #这个元素相当于这个递增子序列长度的起始点,因而初始值为1是合理的,否则,计算可能不准。
    dp = [1]*n

    #初始化,便于下面存储和比较最长递增子序列(最长上升子序列)的长度大小。
    max_length=0

    for i in range(1, n):
        for j in range(0, i):
            if A[i]>=A[j] :
                #A[i]大于A[j]后,表示在dp[j]的基础上增加了一个元素,即dp[j] + 1。
                #右侧需要dp[i],使得j在遍历时dp[j]+1与它做比较,始终保留最大的长度。
                #dp[j]是代表i之前的状态值,右侧dp[i]主要是更新后的值,方便dp[j]+1与之比较。
                #通过比较i之前的状态值,并更新保留较大的i状态的值,j循环结束后得到i状态的最长递增子序列的长度。
                dp[i] = max(dp[i],dp[j] + 1)

        if max_length<dp[i]:
            max_length=d