动态规划算法

动态规划

内容写到什么程度才算完结呢？是写到足以对付互联网企业的算法机试吗？还是要达到信息学竞赛基础的级别？都不是，我只研究我感兴趣的内容。

/*
目录：
├───动态规划
│
├───背包模型
|   ├───01背包
|   ├───完全背包
|   ├───滚动数组优化空间复杂度
|   ├───恰装满背包时的最大价值
|   ├───最少硬币组合
|   └───背包杂例
|
├───最长匹配子列问题
|   ├───最长公共子序列
|   ├───最长公共子串
|   ├───最长递增子序列
|   ├───最长递增公共子序列
|   ├───最长递增子串
|   ├───最长公共递增子串
|   ├───最长重复子串之一
|   ├───最长无重复子串
|   ├───最长回文子序列
|   ├───最长回文子串
|   └───最长匹配子列杂例
|
├───KMP算法
|   ├───模式匹配原理与流程
|   ├───前缀表的动态规划
|   ├───基本的实现
|   ├───常数优化与nextval改进（暂略）
|   └───最长重复子串之二（暂略）
|
├───Kadane算法
|   ├───原理与实现
|   └───最大环形子数组和
|
├───组合优化Others
|   ├───活动选择
|   ├───编辑距离
|   ├───通配符匹配
|   ├───正则表达式匹配
|   ├───扰乱字符串
|   ├───跳跃游戏Ⅰ
|   ├───跳跃游戏Ⅱ与优化方案
|   ├───选择数字
|   └───糖果的吃法
|
├───状态压缩动态规划……………………………………………………………………………………计划中
|   ├───国王游戏与状态压缩……………………………………………………………………计划中
|   └───插头动态规划…………………………………………………………………………………计划中
|       ├───哈密尔顿回路………………………………………………………………………计划中
|       └───国王游戏优化方案………………………………………………………………计划中
|
├───时间复杂度优化
|   ├───决策单调性
|   ├───单调队列与单调栈…………………………………………………………………………计划中
|   └───高级数据结构…………………………………………………………………………………计划中
|
├───图上的动态规划………………………………………………………………………………………计划中
|   ├───Dijkstra算法……………………………………………………………………………计划中
|   ├───地下城游戏……………………………………………………………………………………计划中
|   ├───TSP问题…………………………………………………………………………………………计划中
|   └───多段图的最短路径………………………………………………………………………计划中
|
└───其他领域上的应用…………………………………………………………………………………计划中
    └───近似串匹配……………………………………………………………………………………计划中
*/

动态规划（dynamic programming，DP），教科书式的基本DP可以分为以下几个步骤：

1. 明确问题
2. 拆解子问题，定义状态
3. 求解小规模的简单问题
4. 构建状态转移方程
5. 判断复杂度

完成前四个步骤后，相对于树结构而言，可以设计带有备忘录机制的自顶向下搜索的算法，这是一个记忆化搜索；也可以自底向上填入表格。programming被翻译为“规划”，但其实指的是一种表格法。大多数简单问题的表格都是一维或二维的，三维及以上属于高维动态规划，一般是较为困难的问题。

《算法设计与分析》王红梅著：DP将问题分解为若干个子问题，这些子问题应当不是相互独立的。DP在求解一些子问题时会将解保存起来，当在求解其他子问题时恰需要用到该子问题的解，DP会通过查表简单快捷地获取该子问题的解，而不会再一次进行重复的计算。

　　

《Introduction to Algorithms》by Thomas H. Cormen, etc.（十分推荐阅读这本书）：动态规划与分治法相似，都是通过组合子问题的解来求解原问题。不同的是，分治法将问题划分为互不相交的子问题、递归求解子问题，再将解组合起来求出原问题的解，而动态规划则被应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解递归进行，将其划分为更小的子子问题），这种情况下如果考虑分治算法则会做许多不必要的工作，因为分治算法会反复求解那些公共的子子问题，而动态规划对每个子子问题只会求解一次，并将解保存在一张表中，从而避免了在每次求解一个子子问题时都要重新计算的问题。

动态规划常用来解决最优化问题。我们通常按如下4个步骤设计一个动态规划算法：

　　一、刻画一个最优解的结构特征

　　二、递归地定义最优解的值

　　三、计算一个最优解的值，这通常采取自底向上的计算方法

　　四、利用计算出的信息构造一个最优解

在这里，动态规划dynamic programming中的programming指一种表格法，并非编写程序。

……

最优子结构性质：问题的最优解由相关问题的最优解组合而成，而这些子问题可以独立求解。

……

用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最有子结构。因此，某个问题是否适合应用动态规划算法，其是否具有最优子结构的性质是一个很好的线索（当然，具有最优子结构性质也可能意味着问题适合应用贪心策略）。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解，所以我们必须确保考察了最优解中用到的所有子问题。

……

适合运用动态规划方法求解的最优化问题应具备的第二个性质是子问题空间必须足够的“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同子问题的总数是输入的规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称这个最优化问题具有重叠子问题的性质。与之相对的，适合用分治方法求解的问题通常在递归的每一步都生成全新的子问题。动态规划通常这样利用重叠子问题的性质：对每个子问题求解一次，将解存入一张表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。

……

贪心算法与动态规划有许多相似之处，特别是能够应用贪心算法的问题也必须具有最优子结构的性质。贪心算法和动态规划最大的不同在于他并不是首先寻找子问题的最优解然后再在其中进行选择，而是首先做出一步“贪心”选择，即在当时（局部）看来是最优的选择，然后求解选出的子问题，从而不必费心求解所有可能相关的子问题，并重复这个过程。

对一个问题可以应用DP算法的必要条件是数据间的数据结构构成一个有向无环图（directed acyclic graph，DAG）。这是动态规划无后效性的原因。

根据状态转移方程的逻辑而直接设计的算法，时间复杂度为“状态数乘状态转移的开销”。

规定：分析中的表示的名义第行、第列元素，但均可以为，第零行、第零列往往意味着初始化条件。在这样的规定下，实际上表示的第行、第列元素，但由于从第零行、第零列开始计数，所以名义上仍然称表示的第行、第列元素。如果需要表示绝对位置，我会用矩阵表示法表示。

dp = np.zeros([n, m]).astype(int) dp = [[0]*m for _ in range(n)]

浅浅说两句。产生想学动态规划的想法是导师告诉我他们的算法在动态规划耗时太多，所以让我看一看有没有什么可以改进的地方。但在此之前，我对动态规划的理解仅限于它可以用来解决离散的线性规划问题，24年年底我因病休学也无事可做，所以我就开始了动态规划算法的学习，算是“没事找事”。越学越觉得以前在动态规划世界的眼界之小，但同时方向也从贝塞尔方程的动态规划偏向了八股……因为动态规划也是许多互联网八股机试题很爱考的一种题型（所以说初衷真的不是我想跑路去互联网，，，）。动态规划也算是让我第一次明白了计算机科学的应用，我也似乎对算法很有兴趣（就是不知道这次又会坚持几天了），而此前我所做的编程则顶多算是简单数据分析。这篇文章实际上是我的一个动态规划（八股）的学习笔记，分析过程实际上就是我的思考过程。思考错误难以避免，所以有的问题我也重写过很多遍分析。因此，虽然这本质上是一篇学习笔记，但我觉得对初学计算机算法动态规划的人而言，还是有一定价值的，至少比较贴合初学者的思维。在我对动态规划有了新的认识后，我有时也会回过头对当初理解不当的地方进行修正。

有什么不懂或者错误的地方，欢迎与我交流！

背包模型

背包问题是组合问题上DP算法应用的最简单的数学模型之一，也是最经典的数学模型之一，我们就从这里开始吧。

01背包

# 也可以定义一维状态

01背包问题是最典型的DP在求解离散线性规划中的应用。我们有一个容量有限的背包knapsack，设其最大容量为重量。现在有个物品，其中第个物品有着的价值与的重量，我们可以用任何可能的组合方式将物品装进背包，求背包内物品组合的最大总价值。

这是个典型的离散线性规划问题，可以考虑用动态规划求解，数学模型略。DP问题的关键在于找到状态转移方程。为分解问题得到一个个子问题，用表示将前个物品放入假设总容量为的背包时，所有可能的组合使背包内物品总价值最大的价值。依赖于，根据是否放入第件物品，只有两种可能的计算来源：要么来自于且不将第个物品装进背包，要么来自于但将第个物品装进背包：

这样，便只依赖于，从而可以从一个初始条件逐渐递推至所求的最大总价值。所以，有状态转移方程

且若，则

通过这样递推的方式，可以算出背包内物品组合的最大总价值的数值。

递推的过程，相当于在慢慢填满矩阵，矩阵的每一行都需要通过上一行计算得出。

举个例子，设一共有件物品、背包容量最大为，这个物品对应的价值与重量分别为：

	物品1	物品2	物品3	物品4
重量	1	2	3	4
价值	2	4	4	5

如果分别考虑到、的情况，也就是选择前个物品与背包最大容量为的两种情况，会方便程序的处理（作为递推公式的“启动资金”，即初始化），这样的话矩阵就写成，且第一行与第一列元素均为，即：

先考虑矩阵的第二行，分别代表当放入前面个物品时，背包总容量为时背包内物品组合的最大总价值。根据状态转移方程可以算得：

同样地，根据状态转移方程，利用第二行可以算出第三行的值，即

以此类推，最后可以得到完整的矩阵：

矩阵的末位对角元就是所求答案。

将上述流程写成程序，就是下述代码：

# 输入参数
W = 5
perWeight = [1, 2, 3, 4]
perValue = [2, 4, 4, 5]

class KNP:
    # 01背包
    def knp01(self, W, perWeight, perValue):
        DP_ = [[0]*(W+1) for _ in range(len(perWeight)+1)]
        
        for i in range(1, (len(perWeight)+1)):
            for w in range(1, W+1):
                w_ = w - perWeight[i-1]
                DP_[i][w] = DP_[i-1][w] if w_ < 0 else max(DP_[i-1][w], DP_[i-1][w_]+perValue[i-1])  # 状态转移方程
        return DP_

dp = KNP()
dpMatrix = dp.knp01(W, perWeight, perValue)

该算法的时间复杂度与空间复杂度均为。

print(dpMatrix)

输出：

[[0, 0, 0, 0, 0, 0],
 [0, 2, 2, 2, 2, 2],
 [0, 2, 4, 6, 6, 6],
 [0, 2, 4, 6, 6, 8],
 [0, 2, 4, 6, 6, 8]]

print(dpMatrix[-1][-1])

输出：

8

---

为什么01背包问题不能通过计算每件物品的性价比，按性价比顺序先让性价比最高的物品进入背包呢？这是因为进入背包的物品的数量不可以是分数可以恰好把背包装满，只能是个或者个，再加上背包的容量是有上限的，这就使得一昧选择局部最优解很有可能得不到全局最优解。用一个形象的说法讲就是：往酒瓶里装尽可能重的石块与石子，不是将石头从大到小依次装入就好，因为石头间存在缝隙（我们只能决定石头是否装入瓶中，而不能截掉石头取一部分入瓶），本质上其实是我们希望让瓶子里的剩余空间最小，这时就装入了最多体积的石头，瓶子获得了最大的质量。换言之，如果采取贪心策略，缝隙的存在导致整个瓶子内实际上的每单位容量对应价值降低了。如果是分数背包问题，就可以这样考虑，这也是贪心算法的一个十分基础而典型的应用。

完全背包

# 也可以定义一维状态

完全背包问题：在一次组合中，每个物品至多只能放入背包一次，也就是说每个物品要么放入背包、要么不放入背包，对应只有0和1两种状态。如果只要背包容量足够，每个物品都可以被无限次放入背包，这就是一个完全背包问题。这时，可以把物品编号视为物品的种类。例如，设正数，其中是一系列可以重复出现的完全平方数，问等式成立所需要的最少数量完全平方数是多少个？这个问题的数学模型就是一个完全背包。

这种情况下，的计算来源为：

状态转移方程为

且若，则

尽管式与式是相等的，但式更为简洁，如果从式出发编写算法，则需要遍历求出，此外还要进行多次最大值的比较，但实际上就是的最大元素，所以只需要比较与就可以计算出，而不需要具体地计算出。如果一定要用式当作状态转移方程并在算法中计算，也是可行的，只不过计算机会需要更多时间。

从状态转移方程不难看出，对于01背包与完全背包而言，外循环是还是都无关紧要，内外循环可以交换次序。不同的是，01背包中可以正序扫描或逆序扫描，而完全背包中则只能正序扫描，因为的计算依赖于。

# 输入参数
W = 4
perWeight = [1, 3, 4]
perValue = [15, 20, 30]

class KNP:
    # 完全背包
    def comknp(self, W, perWeight, perValue):
        DP_ = [[0]*(W+1) for _ in range(len(perWeight)+1)]
        
        for i in range(1, len(perWeight)+1):
            for w in range(1, W+1):
                w_ = w - perWeight[i-1]
                DP_[i][w] = DP_[i-1][w] if w_ < 0 else max(DP_[i-1][w], DP_[i][w_]+perValue[i-1])  # 状态转移方程
        return DP_

dp = KNP()
dpMatrix = dp.comknp(W, perWeight, perValue)

该算法的时间复杂度与空间复杂度均为。

print(dpMatrix)

输出：

[[0, 0,  0,  0,  0],
 [0, 15, 30, 45, 60], 
 [0, 15, 30, 45, 60], 
 [0, 15, 30, 45, 60]]

print(dpMatrix[-1][-1 ])

输出：

60

滚动数组优化空间复杂度

# 利用滚动数组的方法，实质上等价于直接将两个背包模型中的状态定义为一维数组

空间优化一般有三种常见手段，分别是空间复用、信息扩展与信息压缩，他们的典型代表分别为滚动数组、迷宫寻路技巧与状态压缩DP。这里考虑滚动数组：注意到算法并不需要完整记录下的每一个元素，因为最终需要的只是末位末位对角元，而计算该对角元只需要上一行的各个元素，计算上一行的各个元素又只需要上上一行的各个元素……因此，每次计算都只会用到上一行的元素，这使得我们不必记录下全部数据。

01背包问题算法利用滚动数组可优化为：

# 输入参数
W = 5
perWeight = [1, 2, 3, 4]
perValue = [2, 4, 4, 5]

class KNP:
    # 01背包
    def knp01(self, W, perWeight, perValue):
        DP_ = [0 for _ in range(W+1)]
        print(DP_)
        
        for i in range(1, len(perWeight)+1):
            for w in range(W, 0, -1):  # 这里需要逆序，因为根据状态转移方程，设w'>w，则计算DP[i][w]不需要用到任何可能的DP[i][w']
                w_ = w - perWeight[i-1]  # 否则有可能会出现用DP[i][w]计算DP[i][w']的情况，但实际上应当用DP[i-1][w]计算DP[i][w']
                if w_ >= 0:
                    dp_ = DP_[w_] + perValue[i-1]
                    DP_[w] = max(DP_[w], dp_)  # 滚动数组
            print(DP_)
        return DP_[W]

dp = KNP()
print('\n', dp.knp01(W, perWeight, perValue))

输出：

[0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2]
[0, 2, 4, 6, 6, 6]
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]


8

完全背包问题算法利用滚动数组可优化为：

# 输入参数
W = 4
perWeight = [1, 3, 4]
perValue = [15, 20, 30]

class KNP:
    # 完全背包
    def comknp(self, W, perWeight, perValue):
        DP_ = [0 for _ in range(W+1)]
        print(DP_)
        
        for i in range(1, len(perWeight)+1):
            for w in range(1, W+1):  # 这里不能逆序，而只能正序——是否应当逆序是对应状态转移方程决定的
                w_ = w - perWeight[i-1]
                if w_ >= 0:
                    dp_ = DP_[w_] + perValue[i-1]
                    DP_[w] = max(DP_[w], dp_)  # 滚动数组
            print(DP_)
        return DP_[W]

dp = KNP()
print('\n', dp.comknp(W, perWeight, perValue))

输出：

[0, 0, 0, 0, 0]
[0, 15, 30, 45, 60]
[0, 15, 30, 45, 60]
[0, 15, 30, 45, 60]


60

改进后的两种算法的空间复杂度均为。

恰装满背包时的最大价值

重要表示技巧：如果状态中存在不可达情况，由于状态转移方程应普遍适用于除初始化条件外的状态转移计算，因此只需要对不可达的基解状态赋原本为不可达的值（实际上利用率动态规划的无后效性），就可以将所有不可达状态以一些不可达的值表示，最后对这些状态不予考虑即可。对于大多数以当下最大价值、匹配子串最大长度等方式所定义的状态，状态一般有限并且状在态转移的计算中伴随取最值操作，这时往往可以通过对那些不可达的基解赋以表示状态不可达。

---

先讨论01背包的情况。在01背包算法的基础上，只需要令DP_初始化时除了第一项为外、其他项均为即可（或者一个很小的负数）。这是因为，初始化后的DP_代表着，即选取前个物品时、假设背包容量为时的价值，这种情况下可以认为当容量也为时背包恰好装满，这时是有价值的（尽管价值为），因此DP_[0]为；而背包容量大于时，由于装进了个物品，所以背包并没有恰装满，这时对于要求而言是没有价值的，故令后续元素的值为（换句话说，永远不会被max函数return——除非两个参数均为，这意味着背包未被填满、值为的情况被视为无效数据）。根据状态转移方程，由于都是由计算而来，因此只需要改变初始化条件就可以让算法仅在恰装满背包时取有效数据，否则值为。

# 输入参数
W = 4
perWeight = [1, 2, 3]
perValue = [2, 4, 1]

class KNP:
    # 恰好装满的01背包
    def knp01_fill(self, W, perWeight, perValue):
        DP_ = [-float('inf') for _ in range(W+1)]
        DP_[0] = 0
        print(DP_)
        
        for i in range(1, len(perWeight)+1):
            for w in range(W, 0, -1):  # 这里需要逆序，因为根据状态转移方程，设w'>w，则计算DP[i][w]不需要用到任何可能的DP[i][w']
                w_ = w - perWeight[i-1]  # 否则有可能会出现用DP[i][w]计算DP[i][w']的情况，但实际上应当用DP[i-1][w]计算DP[i][w']
                if w_ >= 0:
                    dp_ = DP_[w_] + perValue[i-1]
                    DP_[w] = max(DP_[w], dp_)  # 滚动数组
            print(DP_)
        # if DP_[W] < 0:
        #     return -1
        return DP_[W]

dp = KNP()
print('\n', dp.knp01_fill(W, perWeight, perValue))

输出：

[0, -inf, -inf, -inf, -inf]
[0, 2, -inf, -inf, -inf]
[0, 2, 4, 6, -inf]
[0, 2, 4, 6, 3]
3

W = 8
perWeight = [2, 3, 4]
perValue = [2, 4, 1]

print('\n', dp.knp01_fill(W, perWeight, perValue))

输出：

[0, -inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf]
[0, -inf, 2, -inf, -inf, -inf, -inf, -inf, -inf]
[0, -inf, 2, 4, -inf, 6, -inf, -inf, -inf]
[0, -inf, 2, 4, 1, 6, 3, 5, -inf]

-inf

完全背包的情况类似，只需要改变初始化条件：

# 输入参数
W = 8
perWeight = [2, 3, 4]
perValue = [2, 4, 1]

class KNP:
    # 恰好装满的完全背包
    def comknp_fill(self, W, perWeight, perValue):
        DP_ = [-float('inf') for _ in range(W+1)]
        DP_[0] = 0
        print(DP_)
        
        for i in range(1, len(perWeight)+1):
            for w in range(1, W+1):  # 这里不能逆序，而只能正序——是否应当逆序是对应状态转移方程决定的
                w_ = w - perWeight[i-1]
                if w_ >= 0:
                    dp_ = DP_[w_] + perValue[i-1]
                    DP_[w] = max(DP_[w], dp_)  # 滚动数组
            print(DP_)
        # if DP_[W] < 0:
        #     return -1
        return DP_[W]

dp = KNP()
print('\n', dp.comknp_fill(W, perWeight, perValue))

输出：

[0, -inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf]
[0, -inf, 2, -inf, 4, -inf, 6, -inf, 8]
[0, -inf, 2, 4, 4, 6, 8, 8, 10]
[0, -inf, 2, 4, 4, 6, 8, 8, 10]
10

---

这里还有另一个很好的例子。问题描述为：小荣喜欢分享他的日常生活。他有个事件可以选择分享，分享第个事件需要花费的时间和的精力来编辑文案，并能够获得的快乐值。小荣想知道，在总花费时间不超过且总花费精力不超过的前提下，他最多可以获得多少快乐值。

定义状态表示前天在剩余精力、剩余时间时小荣能获得的最大总快乐值。不难分析出，状态转移方程为 显然，我们的状态中存在一些不可达的情况。对于固定的一天，任意指定，很有可能是无论如何也不可到达的状态。利用状态转移的无后效性并根据状态的定义，我们只需要考虑对时的不可达状态赋值，然后遍历进行状态转移的计算即可。也就是说，在第天时，这时不可以选择是否在今天分享日常生活（可以视为只能选择不分享今日日常），所以理论上剩余精力、剩余时间一定均只可能取最大值，对于实际程序中其余取值的状态则视为不可达值，赋。

按上述分析，有

# 二维数组的最大值
def maxnums(nums):
    maxnumber = nums[0][0]
    for sub in nums:
        maxnumber = max(maxnumber, max(sub))
    return maxnumber

class Solution:
    # 分享日常
    def dailyLifeSharing(self, n, T, H, t, h, a):
        dp = [[[-float("inf")]*(T+1) for i in range(H+1)] for j in range(n+1)]  # 对DP[0]初始化-infty
        dp[0][H][T] = 0  # 除DP[0][H][T]赋0

        for i in range(1, n+1):
            for j in range(H+1):
                for k in range(T+1):
                    dp[i][j][k] = dp[i-1][j][k]
                    if j+h[i-1] <= H and k+t[i-1] <= T:
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j+h[i-1]][k+t[i-1]]+a[i-1])

        return maxnums(dp[-1])

最少硬币组合

# 这是一个很好的例题，但背包模型的其他相关问题就不展示了，因为本质上都可以套用背包模型解决

最少硬币组合就是一个典型的基于背包模型的问题，以该问题为例，展示背包模型与动态规划的灵活运用。

最少硬币组合是这样一个有趣的问题：给你多种不同面值的硬币，每种硬币的数量是无限，现在要求使用最少数量的硬币以凑出给定的总金额，并给出一个具体的组合方案。例如：给你三种硬币，面值分别为、与，你需要凑出总金额为。一种最优的方案是使用三枚面值的硬币、一枚面值的硬币和一枚面值的硬币，总共五枚硬币。

显然该问题属于一个恰装满背包的完全背包模型。由于要求所需的硬币最少，所以状态应该是越低越好的“代价”而不是越高越好的“奖励”——这一点很容易做到，只需要将完全背包模型中的价值均设为负即可。在这个问题中，可以将所有硬币的价值均设为以表示所用硬币的计数，最后将结果取相反数即为我们所花费的硬币。例如，针对本文中所举的例子，可以调用如下代码计算使用硬币的个数：

import numpy as np

target = 18
denomination = [1, 2, 5]
forfeit = [-1, -1, -1]

least_amount_of_coins = KNP()
optimum = int(least_amount_of_coins.comknp_fill(target, denomination, forfeit))
print(-optimum)

可以得到输出：

5

接下来的问题是，该怎么找出这具体的五个硬币呢？也可以说，在背包模型中，如何找出背包内物品价值最大化时背包内物品的组合？

---

这里给出一个重要的经验总结：对于组合优化问题，通常而言我们会以“最大容量为时背包里物品的最大价值”、“前个字符匹配的子列长度”与“前天旅程中购买食物的开销”等等这样的单值函数来定义状态函数，这时的表可能是价值表、长度表与消费历史表，但总归是一些单值表，许多时候这样的表不会直接告诉我们每一个表格中的数学模型子最优解所对应的究竟是原问题的哪些组合。一般而言，我们可以通过在计算状态转移时记录状态从何处转移而来，或是在计算完整个表后根据状态转移方程再从最优解向着初始条件逆向寻找状态从何处转移而来，以达到找出原问题的最优组合的目的。

例如，完全背包模型的状态转移方程为 如果而，我们就认为从转移而来；如果而，我们就认为从转移而来；如果，我们就认为从与转移而来。如果代表最优方案的状态自状态转移而来，则意味着状态对应的组合是在状态对应的组合基础上进行相应增删与替换得到的，具体的增删替换由具体的问题与状态定义唯一确定；我们只需要再继续寻找状态自何处转移而来，不断地寻找“源头”——初始条件，或者说基解，就可以给出最优组合。

这样讲未免还是抽象了些，所以这里以最少硬币组合问题为例子，演示如何找出最优组合。演示采取计算状态转移时记录状态从哪转移而来的办法，为此我们需要对完全背包模型的代码进行一些改造。

首先，两个背包模型对应的状态转移方程要记住：

由于该问题属于恰装满背包的完全背包模型，所以采取第二个递推式作为状态转移方程。为方便展示与解释，这里就不使用滚动数组的方法了。

# 输入参数
target = 18
denomination = [1, 2, 5, 20]

class KNP:
    # 最少硬币组合
    def leastAmountOfCoins(self, target, denomination, forfeit=None):
        denomination.sort()
        category = len(denomination)
        if forfeit == None:
            forfeit = [-1 for _ in range(category)]

        dp = [[0]*(target+1) for _ in range(category+1)]  # DP表
        coin_history = [[0]*(target+1) for _ in range(category+1)]  # 记录状态从何处转移而来
        # for i in range(category+1):
        #     dp[i][0] = 0
        for j in range(1, target+1):
            dp[0][j] = -float('inf')
        
        for i in range(1, category+1):  # i：硬币面值遍历
            for j in range(1, target+1):  # j：所凑金额遍历

                res = j - denomination[i-1]  # 剩余凑金额residue
                a = dp[i-1][j]
                dp[i][j] = a
                # if res < 0:
                #     coin_history[i][j] = 0  # 硬币i的面值超过了当前剩余凑金额，不考虑

                # else:
                #     b = dp[i][res] + forfeit[i-1]

                #     if a > b:
                #         coin_history[i][j] = 0  # 一枚硬币i尚不足以恰凑齐当前所需金额，不考虑
                #     elif a < b:
                #         dp[i][j] = b  # 硬币i的面值恰等于当前剩余凑金额，记录当前所使用的硬币
                #         coin_history[i][j] = 1  # 如果用一维数组定义DP表，则这里需要保存i，而不能只是赋1
                #     else:
                #         '''
                #         这种情况一般不会出现，除非给定的硬币中有两个及以上相同的面值，
                #         如果要考虑这一情况，就需要用二叉树记录来个不同的来源，
                #         否则，状态转移的来源是唯一的。
                #         '''
                #         pass
                '''
                以上注释代码的功能等价于下面的代码，
                如果理解不了下面的代码，可以回到注释中的代码进行查看，
                被注释的代码是按完整的逻辑原封不动实现的；
                下面的代码只是在被注释代码基础上省去了在初始化条件np.zeros(...)下不需要的赋值步骤。
                '''
                if res >= 0:
                    b = dp[i][res] + forfeit[i-1]
                    if a < b:
                        dp[i][j] = b
                        coin_history[i][j] = 1
        
        '''
        接下来的代码负责从coin_history中找出最优解的硬币组合，
        思路是面额从大到小，以当前凑金额为边界，让较大面额硬币的数量在合法的条件下最大化，
        再以剩下的凑金额为边界，让较小面额硬币的数量在合法的条件下最大化，
        如此往复，让更小面额硬币的数量在合法的条件下最大化，直到找出最优组合。
        动态规划帮助我们找到了合法的条件，如果不考虑合法条件而直接进行下方的代码的逻辑，
        相当于认为coin_history的内容都等于1，这样只会得到一个不正确的贪心策略与一个错误的结果。
        '''
        combine = []
        i = category
        j = target
        while i > 0:
            if coin_history[i][j] == 0:
                i -= 1
            else:
                combine.append(denomination[i-1])
                j -= denomination[i-1]

        return -dp[-1][-1], combine
                
        
least_amount_of_coins = KNP()
quantity, combine = least_amount_of_coins.leastAmountOfCoins(target, denomination)
print(quantity, '\n', combine)

算法的时空复杂度同完全背包模型的算法，输出为：

5
[5, 5, 5, 2, 1]

代码中的coin_history就帮助我们记录了状态从何处转移而来。对于最少硬币组合问题，我们只关心一枚硬币的面值恰等于当前剩余凑金额时的状态从何处转移而来，即DP[i][j]是否由DP[i][res]转移而来：当coin_history[i][j]的值为，意味着DP[i][j]从DP[i][res]转移而来，否则从其他状态转移而来。这样，我们就可以按照代码中注释所讲解的思路从coin_history中找出最优解的硬币组合了。

---

也可以将表定义为一个一维数组，这样coin_history就需要改为记录当前的值，而不能只赋。以下代码引用自中等题：最优硬币组合问题：

def solution(array, total):
    # 初始化 dp 数组和 coin_used 数组
    dp = [float('inf')] * (total + 1)
    coin_used = [-1] * (total + 1)
    dp[0] = 0

    for coin in array:
        for j in range(coin, total + 1):
            if dp[j - coin] + 1 < dp[j]:
                dp[j] = dp[j - coin] + 1
                coin_used[j] = coin

    if dp[total] == float('inf'):
        return []

    result = []
    while total > 0:
        result.append(coin_used[total])
        total -= coin_used[total]

    return result

背包杂例

暂略，有空了再整理

• 多重背包：每周一算法：背包问题（三）多重背包
• 分组背包：每周一算法：背包问题（四）分组背包，思路是转化为01背包问题
• 背包方案数：每周一算法：背包问题（五）求解方案数，关键在找到状态转移方程

以下问题均系01背包模型：

• 力扣 416：分割等和子集
• 力扣 1049：最后一块石头的重量 II
• 力扣 494：目标和
• 力扣 474：一和零

以下问题均系完全背包模型：

• 力扣 518：零钱兑换 II
• 力扣 377：组合总和 Ⅳ
• 力扣 70：爬楼梯
• 力扣 322：零钱兑换
• 力扣 279：完全平方数
• 力扣 139：单词拆分

最长匹配子列问题

这里只例举几个我最感兴趣与我认为最有代表性的问题。

最长公共子序列

这里先给出一个重要的经验总结：对于这类限制条件下最长匹配子序列 / 子串的动态规划问题，尤其是字符串的匹配问题，通常会首先尝试定义为原序列 / 原字符串的前个元素构成的子列 / 子串中满足限制条件的最长匹配子序列 / 子串长度（如果是寻找两序列 / 字符串的限制条件下的最长公共匹配子序列 / 子串，则定义二维数组，指针分别指向两个原序列 / 字符串）。对于不少问题，找出状态转移方程后，通过动态规划的方法就可以算出最长匹配子序列 / 子串的长度。如果不仅需要长度，还需要求出该最长匹配子序列 / 子串在原序列 / 字符串中的下标，则寻找状态自何处转移即可——这一点在前文“最少硬币组合”小节中有重点解释，这里就不再赘述了。

要寻找两个序列的最长公共子序列（the longest common subsequence，LCS），可以用动态规划解决。按照基础动态规划五步法分析问题，寻找状态转移：

1. 明确问题：给定序列seq_1与seq_2（长分别为），寻找他们的最长公共子序列。应当注意区分，子串需要在原序列中按绝对的顺序连续，而子序列不需要，只需要保持元素间的相对顺序关系，所以最长公共子序列是唯一的。这应当是一个二维动态规划问题。

2. 拆解子问题，定义状态：定义状态为seq_1的前个元素与seq_2的前个元素的最长公共子序列的长度；同时，为方便找到具体的最长公共子序列，在状态的基础上额外定义表示自何处转移而来。对于不难想到，如果seq_1的第个元素等于seq_2的第个元素，那么seq_1的第i个元素就理应在两个子序列的最长公共子序列之中，而且位于末位，因此这时有；否则，以作为基准进行考察，显然应有 那么，何时，何时又有呢？不妨逆向思考，记最长公共子序列长度函数为，对于序列与，他们的最长公共子序列长度为。现在考虑以下三种情形：

   • 如果我们单独为在末位增加一个元素，使之成为，则或

   • 如果我们单独为在末位增加一个元素，使之成为，则或

   • 如果我们同时为在末位增加一个元素，使之成为。若新增的元素相同，那么我们可以直接断言，这意味着，从而有下述关系式成立 这表明，当新增的元素不同时，要么，要么。可以证明后者是不可能存在的情况，因为若，则说明对单独在末位增加元素并不能使最长公共子序列长度增加，此时若还有，则说明尽管单独在末位增加元素无法使最长公共子序列长度增加，但同时在末位增加元素却可以做到，这一点当且仅当在新增元素相同时发生，然而我们此刻的前提为新增的元素不同，矛盾，所以这时只可能有。

   回到状态转移的讨论中，实际上对应前文思考中的、对应前文思考中的。根据思考的分析可知，如果seq_1的第个元素不等于seq_2的第个元素，则。

   综上所述，的状态转移为： 根据状态转移，定义以表示状态从何处转移而来： 需要注意的是，虽然为了简便起见，我们在的状态转移中使用了一个函数，但实际上取最大值的表达式中蕴含了两处不同的状态转移来源，即与，因此在记录时，需要用两个不同的属性数据分别表示这两个状态来源（在上式的定义中，我们是用来表示的）。

3. 求解小规模的简单问题：

4. 构建状态转移方程：如果将考虑在内， 如果只需要计算最长公共子序列的长度，可以忽略。

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。

# 输入参数
seq_1 = 'kabtcdefj'
seq_2 = 'jfacdgtestj'

class Seq:
    # 最长公共子序列
    def lcs_seq(self, seq_1, seq_2):
        n = len(seq_1)
        m = len(seq_2)

        L = [[0]*(m+1) for _ in range (n+1)]
        S = [[0]*(m+1) for _ in range (n+1)]
        
        for row in range(1, n+1):
            for column in range(1, m+1):
                if seq_1[row-1] == seq_2[column-1]:
                    L[row][column] = L[row-1][column-1] + 1
                    S[row][column] = 0
                elif L[row][column-1] >= L[row-1][column]:
                    L[row][column] = L[row][column-1]
                    S[row][column] = 1
                else:
                    L[row][column] = L[row-1][column]
                    S[row][column] = 2
        print(L, '\n\n', '-'*37, '\n\n', S, '\n')
        # 到这里就已经计算出最长公共子序列的长度了，以下为根据S搜索具体的最长公共子序列代码

        # 搜索过程
        k = L[n][m]  # 最长公共子序列长度、lcsSeq填充位置的下标
        x = n  # 搜索点横坐标
        y = m  # 搜索点纵坐标
        index_seq_1 = [0 for _ in range(k)]  # 记录seq1下标
        index_seq_2 = [0 for _ in range(k)]
        lcsSeq = [None for _ in range(k)]
        i = 0
        while x > 0 and y > 0:
            if S[x][y] == 0:
                lcsSeq[k-1] = seq_2[y-1]
                index_seq_1[k-1] = x-1
                index_seq_2[k-1] = y-1
                k -= 1
                x -= 1
                y -= 1
            elif S[x][y] == 1:
                y -= 1
            else:
                x -= 1
        return lcsSeq, index_seq_1, index_seq_2

lcs = Seq()
print(lcs.lcs_seq(seq_1, seq_2))

该算法的时间复杂度与空间复杂度均为。空间复杂度应该还可以做到更优，但也会使过程更繁琐。

输出：

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2],
 [0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2],
 [0, 0, 0, 1, 2, 3, 3, 3, 3, 3, 3, 3],
 [0, 0, 0, 1, 2, 3, 3, 3, 4, 4, 4, 4],
 [0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4],
 [0, 1, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5]] 

-------------------------------------

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 2, 1, 1, 1, 0, 1, 1, 0, 1],
 [0, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 2, 2, 0, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 2, 2, 2, 1, 1, 0, 1, 1, 1],
 [0, 1, 0, 1, 2, 2, 1, 1, 2, 1, 1, 1],
 [0, 0, 1, 1, 2, 2, 1, 1, 2, 1, 1, 0]] 

(['a', 'c', 'd', 'e', 'j'], [1, 4, 5, 6, 8], [2, 3, 4, 7, 10])

最长公共子串

是否可以用正则表达式实现？

最长公共子序列由于不要求连续的性质，是唯一的；而最长公共子串（the longest common substring，LCS）则可能存在多个。

动态规划是大厂的热门考点，其中最长公共子串与最长公共子序列这两道题出现得尤其频繁，这两道题其实有挺多变种，很适合考察侯选人对动态规划的掌握情况。

还是按照五步法来分析问题：

1. 明确问题：给定两个序列str_1与str_2（长度分别为、），寻找他们的最长公共子串。公共子串的性质是公共子串必须同时是两个原序列的顺序连续切片，我们需要找到最长公共子串。这应当是一个二维动态规划问题。

2. 拆解子问题，定义状态：注意到子串在原序列中必然是连续的，所以想到可以定义状态为同时以str_1[:i]与str_2[:j]作为末位元素的最长公共子串的长度，和最长公共子序列问题中的定义相似，这里是形矩阵，从第零行、第零列开始计数。

   这样定义状态的好处是利用了最长公共子串必然连续的性质分解问题——只要知道了最长公共子串的长度与最长公共子串中最后一个元素在原序列中的位置，那么在原序列的该位置处向前数最长公共子串长度个元素，就得到了最长公共子串。其中最后一个元素在原序列中的位置可以通过相邻元素的增减情况获知，于是问题被分解为若干个子问题。

   于是不难写出的状态转移： 此外，如果除了最长公共子串长度外还要求给出具体的最长公共子串，则不需要仿照最长公共子序列问题的做法、在计算状态转移时记录转移来源。因为子串具有连续的性质，所以只需要根据表对最大取值点按所在行或所在列向前数最大取值个位置，就可以得到子串在两个原字符串中的下标了。

3. 求解小规模的简单问题：

4. 构建状态转移方程：

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。在实际的实现中，可以使用滚动数组的办法降低空间复杂度。

# 输入参数
seq_1 = 'abcd123'
seq_2 = 'abcef012345'


# 返回数组最大值下标序列
def argmax(nums):
    # if len(nums) == 0:
    #     return None, None
    index = [0]
    max_num = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > max_num:
            max_num = nums[i]
            index = [i]
        elif nums[i] == max_num:
            index.append(i)
    return max_num, index

class Seq:
    # 最长公共子串
    def lcs_str(self, seq_1, seq_2):
        n = len(seq_1)
        m = len(seq_2)
        # dp = np.zeros([n+1, m+1]).astype(int)
        dp_1 = [0 for _ in range(m+1)]  # 滚动数组1
        dp_2 = [0 for _ in range(m+1)]  # 滚动数组2

        # # 计算DP矩阵
        # for row in range(1, n+1):
        #     for column in range(1, m+1):
        #         if seq_1[row-1] == seq_2[column-1]:
        #             dp[row][column] = dp[row-1][column-1] + 1
        # print(dp)

        # 用滚动数组代替DP矩阵，这一段代码是上段注释掉的优化版本，减小了内存开销
        max_len = 0  # 记录目前所有搜索中已知的最长公共子串的长度
        x = []  # 记录当前行搜索中符合已知的最长公共子串的长度的子串末位元素横坐标
        y = []  # 记录当前行搜索中符合已知的最长公共子串的长度的子串末位元素纵坐标
        for row in range(1, n+1):
            for column in range(1, m+1):
                if seq_1[row-1] == seq_2[column-1]:
                    dp_2[column] = dp_1[column-1] + 1
            row_max_len, row_x = argmax(dp_2)  # 返回当前行搜索最大值与最大值下标序列
            if max_len < row_max_len:  # 将当前行搜索最大值与目前已知搜索最大值比对
                max_len = row_max_len
                x = row_x
                y = [row for _ in range(len(row_x))]
            elif max_len == row_max_len:
                x.extend(row_x)
                y.extend([row for _ in range(len(row_x))])
            dp_1 = dp_2
            dp_2 = [0 for _ in range(m+1)]

        # 根据最大值在DP中的坐标与最长公共子串长度，返回最长公共子串序列及其在原序列中末位的下标序列
        lcsStr = []
        lcsIndex = [y, x]
        for i in range(len(x)):
            lcsStr.append(''.join(seq_1[y[i]-max_len:y[i]]))
        return lcsStr, lcsIndex


lcs = Seq()
result, _ = lcs.lcs_str(seq_1, seq_2)
print(result)

该算法的时间复杂度为，同时由于采取了滚动数组的方法，空间复杂度为。

输出：

['abc', '123']

最长递增子序列

对于状态与状态转移方程不太明显的问题，还是按五步法来一步步分析。

1. 明确问题：最长递增子序列问题（the longest increasing subsequence，LIS），是指给定的一组长为数字序列seq，按照从左向右顺序，由递增的数字组成的子序列（这些数字在原序列中不必连续出现）中，取长度最大的子序列为最长递增子序列。这应当是一个一维动态规划问题。

2. 拆解子问题，定义状态：这里对状态的定义可以参考最长公共子串问题中定义的状态，因为这两个问题都可以被视作对子列加上了更多限制的最长公共子序列问题。

   由于这是一个一维动态规划问题，所以设状态为（这里），类似于最长公共子串问题中的定义，定义为以为末位元素的最长递增子序列的长度，那么一定与有关，因为对应的元素是，我们只要能找到前个元素中满足不大于的最大元素（如果存在与之等大的元素，则取值最大者），假设这个元素位于的第位，那么显然就有，因为在一个包含且是最大元素的递增子序列中，能且只能位于末尾处，否则序列就不是递增序列了——这就利用到了递增子序列递增的性质。根据分析，可以写出的计算公式： 算出后，现在的问题是如何通过找出seq的最长递增子序列。举一个具体的例子，这里为方便起见考虑数字范围为到，对于一个数字字符串'3091582079'，元素与对应的下标为： 他的数组为： 经观察可知，要寻找最长递增子序列，自然是从最大的出发，因为这意味着对应的元素是长度最长的递增子序列的末位元素，因此可以通过最大的先确定出最长递增子序列的最后一位，不妨记最大的为。接下来，逆着的状态转移方程，找到，从每一个算出的就是以为倒数第一位元素的最长递增子序列倒数第二位对应的全部可能的下标。再逆着的状态转移方程对进行同样的操作，循环往复，最终得到全部的最长递增子序列。

3. 求解小规模的简单问题：

4. 构建状态转移方程： 如果要求严格递增，则将状态转移方程中的改为。

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。由于要找出全部的最长递增子序列的具体值最好用树的数据结构逐级运算，但这又需要先实现一颗多叉树，相对会麻烦一些，这与本文的主题——动态规划也没有太大关系，所以这里只实现返回最长递增子序列长度，并打印数组。

# 输入参数
seq = '3091582079'


# 返回数组最大值下标序列
def argmax(nums):
    # if len(nums) == 0:
    #     return None, None
    index = [0]
    max_num = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > max_num:
            max_num = nums[i]
            index = [i]
        elif nums[i] == max_num:
            index.append(i)
    return max_num, index

def argmax_lis(nums):
    if len(nums) == 0:
        return 0, 0
    return argmax(nums)

class Seq:
    # 最长递增子序列
    def lis_seq(self, seq):
        N = len(seq)
        dp = [0 for _ in range(N)]
        
        for n in range(N):
            dp_i = []
            for i in range(n):
                if seq[i] <= seq[n]:
                    dp_i.append(dp[i])
            max_dp_i, _ = argmax_lis(dp_i)
            dp[n] = max_dp_i + 1
        print(dp)
        
        lis_len, _ = argmax(dp)
        return lis_len


lis = Seq()
print(lis.lis_seq(seq))

该算法的时间复杂度为，空间复杂度为。算法的运行效率是比较慢的，有办法从状态转移方程入手，组合运用先进算法大大降低时间复杂度，这将在后文“动态规划算法优化”一章中再具体介绍。

输出：

[1, 1, 2, 2, 3, 4, 3, 2, 4, 5]
5

---

对状态转移方程稍作修改，即对程序中的if seq[i] <= seq[n]:与dp[n] = max_dp_i + 1稍加改动，就可以得到不同的最长递减子序列（改为）、最长严格递增子序列（改为）、最长等差子序列等等。

这里以计算最长等差子序列的长度为例子，修改后的状态转移方程为： 于是可以将程序修改为：

class Solution:
    # 最长等差子数组长度
    def arithmetic(self, seq, difference=1):
        N = len(seq)
        dp = [0 for _ in range(N)]
        dp_max = 1
        
        for n in range(N):
            for i in range(n-1, -1, -1):
                if seq[i] + difference == seq[n]:
                    dp[n] = max(dp[i], dp[n])
            dp[n] = dp[n] + 1
            dp_max = max(dp[n], dp_max)
        return dp_max  # max(dp)

该算法的时间复杂度与空间复杂度同上。

最长公共递增子序列

这个问题的解显然可以借鉴最长公共子序列问题与最长递增子序列问题的算法，是相似但同时了两个问题特征的问题。

1. 明确问题：最长公共递增子序列（the longest common increasing subsequence，LICS），是指给定的两组数字序列seq_1、'seq_2'，长度分别为、，按照从左向右顺序，由递增的数字组成的二者的公共子序列（这些数字在原序列中不必连续出现）中，取长度最大的公共子序列为最长递增子序列。这应当是一个二维动态规划问题。

2. 拆解子问题，定义状态：类似处理，定义状态为同时以与作为末位元素的最长公共递增子序列的长度，只需要对最长递增子序列的状态转移做部分修改就可以得到该问题的状态转移，其中的修改的目的是考虑到子序列是公共的而进行二维化改造，包括仅在时才考虑的值加一、在向前搜寻满足条件的最大值时还要求且：

3. 求解小规模的简单问题：

4. 构建状态转移方程：

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。同样地，简便起见这里只返回最长公共递增子序列的长度并打印表；如果需要最长公共递增子序列的具体序列，仿照最长递增子序列问题中分析的思路进行操作即可。

# 输入参数
seq_1 = '1234567123'
seq_2 = '34567123'


# 返回数组最大值下标序列
def argmax(nums):
    # if len(nums) == 0:
    #     return None, None
    index = [0]
    max_num = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > max_num:
            max_num = nums[i]
            index = [i]
        elif nums[i] == max_num:
            index.append(i)
    return max_num, index

def argmax_lis(nums):
    if len(nums) == 0:
        return 0, 0
    return argmax(nums)

class Seq:
    # 最长公共递增子序列
    def lics_seq(self, seq_1, seq_2):
        n = len(seq_1)
        m = len(seq_2)
        dp = [[0]*(m+1)  for _ in range(n+1)]

        row_max_dp_in_DP = []
        for row in range(1, n+1):
            for column in range(1, m+1):
                if seq_1[row-1] == seq_2[column-1]:
                    column_search_dp_st = []  # 满足第二条件的最大DP值备选列DP值序列，内容为每行满足第二条件的最大DP值
                    for a in range(1, row):
                        row_search_dp_st = []  # 满足第二条件的最大DP值备选行DP值序列
                        for b in range(1, column):
                            if a == row and b == column:
                                break
                            if seq_1[a-1] == seq_2[b-1] and seq_1[a-1] <= seq_1[row-1]:
                                row_search_dp_st.append(dp[a][b])
                        row_max_dp, _ = argmax_lis(row_search_dp_st)
                        column_search_dp_st.append(row_max_dp)
                    max_dp, _ = argmax_lis(column_search_dp_st)
                    dp[row][column] = max_dp + 1
                else:
                    column_search_dp_st = []  # 满足第一条件的最大DP值备选列DP值序列，内容为每行满足第一条件的最大DP值
                    for a in range(1, row):
                        row_search_dp_st = []  # 满足第一条件的最大DP值备选行DP值序列
                        for b in range(1, column):
                            if a == row and b == column:
                                break
                            if seq_1[a-1] == seq_2[b-1]:
                                row_search_dp_st.append(dp[a][b])
                        row_max_dp, _ = argmax_lis(row_search_dp_st)
                        column_search_dp_st.append(row_max_dp)
                    max_dp, _ = argmax_lis(column_search_dp_st)
                    dp[row][column] = max_dp
            this_row_max_dp_in_DP, _ = argmax_lis(dp[row])
            row_max_dp_in_DP.append(this_row_max_dp_in_DP)
        max_dp_in_DP, _ = argmax_lis(row_max_dp_in_DP)
        print(dp, '\n')
        
        return max_dp_in_DP


lics = Seq()
print(lics.lics_seq(seq_1, seq_2))

该算法的时间复杂度为，空间复杂度为。

输出：

[[0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 2, 1],
 [0, 1, 0, 0, 0, 0, 0, 1, 3],
 [0, 0, 2, 1, 1, 1, 1, 1, 2],
 [0, 0, 1, 3, 2, 2, 2, 2, 2],
 [0, 0, 1, 2, 4, 3, 3, 3, 3],
 [0, 0, 1, 2, 3, 5, 4, 4, 4],
 [0, 0, 1, 2, 3, 4, 1, 5, 5],
 [0, 0, 1, 2, 3, 4, 5, 2, 5],
 [0, 1, 1, 2, 3, 4, 5, 5, 3]]


5

最长递增子串

结合最长公共子串算法中对子串性质的利用，以及最长递增子序列算法中对递增性质的利用，很容易解决这个问题。

1. 明确问题：最长递增子串问题（the longest increasing substring，LIS），是指给定的一组长为的数字序列seq，按照从左向右顺序，由在'seq'中连续的递增数字组成的子串中，取长度最大的子串为最长递增子串。这应当是一个一维动态规划问题，其中最长递增子串不一定唯一。

2. 拆解子问题，定义状态：利用到上文中提到的两个性质，不难想到可以定义表示以为末位数字的最长递增子串的长度。然后，只需要找到最大的值，在这些值对应中的元素处向前数最大值个元素，就得到了最长递增子串。的递推关系为： 可以看到，这里的递推关系与最长公共子串问题中的递推关系相比，区别仅仅在于条件中两个数字的序关系不同。

3. 求解小规模的简单问题：

4. 构建状态转移方程：

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。可以用滚动数组的方法降低空间复杂度。

# 输入参数
seq = '012354124563'

class Seq:
    # 最长递增子串
    def lis_str(self, seq):
        N = len(seq)
        current_max_dp = 1
        index_of_current_max_dp = [0]
        dp_n = 0  # 滚动数组
        dp_n_subtract_1 = 0  # 滚动数组
        
        for n in range(1, N):
            if seq[n] >= seq[n-1]:
                dp_n = dp_n_subtract_1 + 1
            if dp_n > current_max_dp:
                current_max_dp = dp_n
                index_of_current_max_dp = [n]
            elif dp_n == current_max_dp:
                index_of_current_max_dp.append(n)
            dp_n_subtract_1 = dp_n  # 滚动数组的实现
            dp_n = 0
        
        lisStr = []
        for i in index_of_current_max_dp:
            lisStr.append(''.join(seq[i-current_max_dp:i+1]))
            
        return lisStr, index_of_current_max_dp
        
lis = Seq()
result, _ = lis.lis_str(seq)
print(result)

该算法的时间复杂度为，同时由于采取了滚动数组的方法，空间复杂度为。

输出：

['01235', '12456']

最长公共递增子串

结合最长公共子串算法与最长递增子串算法，对最长递增子串算法进行二维化改造即可。

1. 明确问题：最长递增子串问题（the longest common increasing substring，LICS），是指给定的两组数字序列seq_1、'seq_2'，长度分别为、，按照从左向右顺序，由在两个数字序列中均连续的递增数字所组成的子串中，取长度最大的公共子串为最长公共递增子串。这应当是一个二维动态规划问题，其中最长公共递增子串不一定唯一。

2. 拆解子问题，定义状态：定义表示同时以与为末位数字的最长递增子串的长度，有 由于公共子串在任何一个原序列中都是连续的，所以算出后对任意一个原序列按最长递增子串问题中最长递增子串的搜寻方法即可得到最长公共递增子串。

3. 求解小规模的简单问题：

4. 构建状态转移方程：

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。可以用滚动数组的方法降低空间复杂度。

# 输入参数
seq_1 = '0123541245693'
seq_2 = '0123591231231245693'


# 返回数组最大值下标序列
def argmax(nums):
    # if len(nums) == 0:
    #     return None, None
    index = [0]
    max_num = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > max_num:
            max_num = nums[i]
            index = [i]
        elif nums[i] == max_num:
            index.append(i)
    return max_num, index


class Seq:
    # 最长递增子串
    def lics_str(self, seq_1, seq_2):
        n = len(seq_1)
        m = len(seq_2)
        dp_current_row = [0 for _ in range(m+1)]  # 滚动数组
        dp_last_row = [0 for _ in range(m+1)]
        dp_max_until_current_row = 0
        index_of_dpmax_row = []
        index_of_dpmax_column = []

        for row in range(1, n+1):
            if seq_1[row-1] == seq_2[0]:
                dp_current_row[1] = 1
            for column in range(2, m+1):
                if seq_1[row-1] == seq_2[column-1]:
                    if seq_1[row-1] >= seq_1[row-2]:
                        dp_current_row[column] = dp_last_row[column-1] + 1
            dp_max_current_row, index_of_dpmax_current_row = argmax(dp_current_row)
            if dp_max_current_row > dp_max_until_current_row:
                dp_max_until_current_row = dp_max_current_row
                index_of_dpmax_row = [row for _ in range(len(index_of_dpmax_current_row))]
                index_of_dpmax_column = index_of_dpmax_current_row
            elif dp_max_current_row == dp_max_until_current_row:
                index_of_dpmax_row.extend([row for _ in range(len(index_of_dpmax_current_row))])
                index_of_dpmax_column.extend(index_of_dpmax_current_row)
            dp_last_row = dp_current_row
            dp_current_row = [0 for _ in range(m+1)]

        licsStr = []
        for i in index_of_dpmax_row:
            licsStr.append(''.join(seq_1[i-dp_max_until_current_row:i]))
        return licsStr, [index_of_dpmax_row, index_of_dpmax_column]


lics = Seq()
result, _ = lics.lics_str(seq_1, seq_2)
print(result)

该算法的时间复杂度为，同时由于采取了滚动数组的方法，空间复杂度为。

输出：

['01235', '24569']

最长重复子串之一

这个问题可以用Rabin-Karp算法解决，Rabin-Karp算法是非常高效的。除了Rabin-Karp算法，还可以使用利用KMP算法、二分查找等等，都可以解决该问题。这个问题不方便直接应用动态规划，因为难以分解出具有最优子结构性质的重叠子问题。

具体而言，最长重复子串（the longest repeating substring，LRS）问题，是指给定一个长为的序列seq，寻找seq所有至少出现两次的子串中长度最大的子串。这个问题不方便直接对seq的元素定义状态并列出状态转移方程，但依然可以在设计算法时利用到动态规划方法。

设计算法解决最长重复子串问题，至少有两种思路：

• KMP算法：KMP算法的关键就是求解数组，针对，可以得到，这个式子恰好意味着重复子串，所以由此求最长重复子串问题就转化为求解数组中最大值问题，而数组的计算实际上就是用前缀表与动态规划完成的。

  这部分的分析与实现，留到后文“模式匹配KMP算法”一章中再作讨论。

• 后缀数组：取seq的各级后缀序列，再对其进行字符串间排序，其中排序可以考虑使用时间复杂度为的快速排序算法，接着计算排序后两两相邻的后缀序列比较前缀公共子串的长度，找到所有相邻后缀序列间的前缀公共子串中长度最大的子串，该子串就是所求的最长重复子串。实际上，KMP算法中计算数组也是基于前缀表的，所以可以说这个问题用前缀数组和后缀数组都可以解决。

这里先只利用后缀数组设计算法，尽管他与动态规划没有太大关系，但在后文中将会用基于动态规划的KMP算法再次解决这个问题。现在可以开始编写程序了。

# 输入参数
seq = 'mnbabc123abc450uio123519'


# 快速排序
def quicksort(seq, pivot_index=0):
    N = len(seq)
    if N <= 1:
        return seq
    pivot = seq[pivot_index]
    less = []
    geq = []

    for n in range(N):
        if n == pivot_index:
            continue
        if seq[n] <= pivot:
            less.append(seq[n])
        else:
            geq.append(seq[n])
    sorted_less = quicksort(less)
    sorted_geq = quicksort(geq)
    return sorted_less + [pivot] + sorted_geq

class Seq:
    # 最长重复子串
    def lrs(self, seq):
        N = len(seq)
        suffix = [seq[i:] for i in range(N)]  # 后缀数组集合
        [print(_) for _ in suffix] + [print('\n') for _ in range(1)]
        suffix = quicksort(suffix)  # 排序suffix，再赋值给suffix
        [print(_) for _ in suffix] + [print('\n') for _ in range(1)]
        lrsStr = []
        lrsStr_len = 0
        for n in range(N-1):
            lcsStr = []
            k = 0
            for i in range(min(len(suffix[n]), len(suffix[n+1]))):  # 寻找相邻排序后suffix的最长公共前缀
                if suffix[n][i] == suffix[n+1][i]:
                    k += 1
                else:
                    lcsStr = [suffix[n][:k]]
            lcsStr_len = len(lcsStr[0])
            if lcsStr_len > lrsStr_len:
                lrsStr = lcsStr
                lrsStr_len = lcsStr_len
            elif lcsStr_len == lrsStr_len:
                lrsStr.extend(lcsStr)
        return lrsStr
        

lrs = Seq()
print(lrs.lrs(seq))

该算法的平均时间复杂度为，空间复杂度为。

输出：

mnbabc123abc450uio123519
nbabc123abc450uio123519
babc123abc450uio123519
abc123abc450uio123519
bc123abc450uio123519
c123abc450uio123519
123abc450uio123519
23abc450uio123519
3abc450uio123519
abc450uio123519
bc450uio123519
c450uio123519
450uio123519
50uio123519
0uio123519
uio123519
io123519
o123519
123519
23519
3519
519
19
9


0uio123519
123519
123abc450uio123519
19
23519
23abc450uio123519
3519
3abc450uio123519
450uio123519
50uio123519
519
9
abc123abc450uio123519
abc450uio123519
babc123abc450uio123519
bc123abc450uio123519
bc450uio123519
c123abc450uio123519
c450uio123519
io123519
mnbabc123abc450uio123519
nbabc123abc450uio123519
o123519
uio123519


['123', 'abc']

最长无重复子串

其实这个问题，我认为用滑动窗口的方法是最合适且直观的，如果只需要算出长度，应用滑动窗口方法的Python码可以参考LCR 167. 招式拆解 I（滑动窗口 + 哈希表，清晰图解）（其中动态规划的思路也很简明清晰），C++的实现可以参考双指针滑动窗口、动态规划、暴力线性遍历，可以做到线性时间复杂度。

如果要应用动态规划方法且只需要计算长度，结合哈希表也可以做到绝对的线性时间复杂度，代码来自上一段的第一个引用链接：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1)  # 获取索引 i
            dic[s[j]] = j  # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i  # dp[j - 1] -> dp[j]
            res = max(res, tmp)  # max(dp[j - 1], dp[j])
        return res

最长无重复子串也是一个对动态规划学习的很有启发性的问题。现在把这一问题当作动态规划问题，按五步法进行分析。

1. 明确问题：最长无重复（字符）子串（the longest substrings without repeating characters，LSWRC）问题，是指给定一个长为的字符串seq，寻找seq的所有不包含重复字符的子串中，长度最长的无重复字符子串。易见最长无重复字符子串不一定唯一。

2. 拆解子问题，定义状态：根据相似问题类似地定义表示以为末位字符的最长无重复字符子串的长度，对于，若且，则记。实际上，这样定义就是为了表示从向前数的第一个与相同的字符的位置。容易知道，从开始到结束的子串是只包含两个字符的子串，所以从开始到结束的子串一定不存在重复的字符。现在可以拆解子问题了，从出发可以得到，从可以得到 得到了，可以推导出： 得到了，可以推导出：

   其中指以结尾的最长无重复子串

   可见，是可以通过状态转移计算的，且只依赖于与。注意到，与之间也存在一些关系：

   • 前文已经分析过，从开始到结束的子串是一定不存在重复字符的子串，而从到的子串又必然不存在重复字符（结合子串连续的性质与的定义推理），所以如果位于之前，则意味着从到的子串均不存在重复字符，否则要么在之后，要么就不意味着以为末位字符的最长无重复字符子串的长度——后者是不可能的，前者则不满足假设，因此这样的情况下，，此时的最长无重复子串为从到的子串。这些关系式蕴含了最优子结构性质，最优解依赖于其子问题最优解。

   • 不过，如果位于或其后，即，则说明尽管从到的子串不存在重复字符，但是一定与从到的子串中的某个字符重复，这是容易理解的，这时——从到的子串不存在重复字符，当然从到的子串也不存在重复字符，但根据的定义，与重复，所以以为末位字符的最长无重复子串就是从到的子串。

   • 至于不存在的情况，说明目前为止从首位字符开始直到都不存在与重复的字符，自然地有，此时的最长无重复子串也是从到的子串。

   现在距离算出表只差最后一个问题：如何寻找？如果用for循环遍历实现则需要回溯子串，那么算法的时间开销相比暴力搜索也没有优化太多太多（暴力搜索的时间复杂度为，而回溯子串的为），相对于滑动窗口方法的线性时间复杂度仍然差了一大截。我们可以用哈希表来解决这个问题，构造如下一个哈希映射：以字符对应的ASCII码作为地址映射到哈希表，值只取或，首先将哈希表中的值全部初始化为，然后将当前最长无重复字符子串（从到的子串）的各个字符进行哈希映射，映射值取，接下来如果要判断是否与当前最长无重复字符子串中的字符重复，只需要将进行哈希映射，如果对应地址的哈希值为，则说明与当前最长无重复字符子串的字符均不重复；如果对应地址的哈希值为，则说明与当前最长无重复字符子串的字符均重复。对于第一种、不存在重复的情况，哈希表可以继续使用，将对应地址的哈希值赋即可；如果是第二种、存在重复字符的情况，则要么回到流程起始处重新构造新的更新最长无重复字符子串的哈希表，要么将从到的子串中各字符对应在哈希表中的值重新赋。这会导致时间复杂度上升至，但如果希望得到具体的最长无重复子串，就不得不这样做，这是为了保证哈希表的值中至多存在一个。若只需要得到最长无重复子串的长度，则可以去掉这一步，将时间复杂度降低至。

   然后，现在我们的哈希表也只能判断是否有重复字符，而不能直接得到，所以我们可以构造一个双层哈希表，只需要在将字符进行哈希映射并赋值作为第一元的同时向该地址处的第二元填入该字符在中的位置参数，并在出现重复元素时将重复元素对应的位置参数更新为即可（最初我并没有考虑到这一点）。这样，当与当前最长无重复子串存在重复时，就等于哈希表中第一元值为位置处的第二元的值

   判断重复元素，是哈希表的妙用之一。所以，我们的解决方案是动态规划哈希表。

3. 求解小规模的简单问题：

4. 构建状态转移方程：

5. 判断复杂度：需要考虑具体的实现方式

现在可以开始编写程序了。同样地，可以用滚动数组节省空间。

# 输入参数
seq = '970267123456789294417148689652041395'

class Seq:
    # 最长无重复字符子串
    def lswrc(self, seq):
        N = len(seq)
        table = [[0]*(127-32) for _ in range(2)]  # ASCII
        dp_max = 0
        dp_max_index = []
        dp_now = 0  # 滚动数组
        dp_last = 0
        
        for n in range(N):
            k = 0
            address = ord(seq[n]) - 32  # 哈希映射
            if table[0][address] == 0:  # 先通过哈希表寻找k
                k = -1
            else:
                k = table[1][address]
                table[1][address] = n

            if k < n - dp_last:  # 更新dp，同时更新哈希表
                dp_now = dp_last + 1
                table[0][address] = 1
                table[1][address] = n
            else:
                dp_now = n - k
                for char in seq[n-dp_last:k]:  # 赋0
                    table[0][ord(char)-32] = 0

            if dp_now > dp_max:
                dp_max = dp_now
                dp_max_index = [n]
            elif dp_now == dp_max:
                dp_max_index.append(n)
            
            dp_last = dp_now

        lswrcStr = [seq[dp_max_index[i]-dp_max+1:dp_max_index[i]+1] for i in range(len(dp_max_index))]
        return lswrcStr, dp_max_index

lswrc = Seq()
result, _ = lswrc.lswrc(seq)
print(result)

该算法的平均时间复杂度，在最坏、最极端的情况下为（基本上不会达到，特别是对于字符集中只存在数字、字母与常用符号的长字符串，根据抽屉原理这样的情况是绝无可能出现的），空间复杂度为。

输出：

['123456789', '896520413']

写这个算法的时候我碰到了两个错误，导致我在这个问题上花费了很多时间，这里记录一下我初次解这个问题时出现的错误：

1. 第31行的for char in seq[n-dp_last:k]:，我最初写成了for char in seq[n-dp_last:k+1]:，下标的使用不正确
2. 起初漏写了第23行的代码，少考虑了情况，当时我以为只需要第28行代码就可以实现哈希表第二行的更新，实际上两行代码均缺一不可，少一个就会漏考虑情况：第23行代码的意义是当第个字符与当前最长无重复子串中的字符重复时，更新第二行哈希表，将位置上的字符所对应的位置参数更新为；第28行代码的意义则是当存在但并不位于当前最长无重复子串中时，在将插入当前最长无重复子串尾部作为新的最长无重复子串时，更新位置参数，可见二者的功能其实完全不同，因为第23行的代码修改的是哈希值原本就为的位置参数，而第28行的代码修改的是哈希值为的、需要赋值为时的位置参数

不过如果只是求最长无重复子串的长度而非所有的最长无重复子串，代码会非常简单，这些错误也不会出现，因为错误对应的代码并不需要实现。

最长回文子序列

# 建议先阅读下一项问题：最长回文子串，再回头阅读本项问题

# 两个问题较为相似，本问题算法基于下一项问题，所以对相似之处不会做过多解释

# 如果理解有困难，先阅读下一项问题

这里是最长回文子序列问题（the longest palindromic subsequence，LPS），和下一项问题最长回文子串一样，这里只计算最长回文子序列的长度，如果需要最长回文子序列的值，则记录表的实际转移状态即可。回文子序列的的特征是当去掉两端最外层的两个字符后，剩余的部分仍构成一个回文子序列。仿照前文的各个例子，定义为字符串中以第个字符作为回文子序列末位字符的子序列长度是不可取的，会发现很难找出状态转移。正确的思路应该参考最长回文子串问题（见后文）中的定义，记给出的字符串为seq且长度为，设表示以为开头并以为结尾的子串的最长回文子序列长度。换言之，等于被指针（其中）“框住”的子串的最长回文子序列长度。

易见，的赋值问题可以被分解为三种互斥的情况：若，，则；若且，则；若且，则。 根据上图来理解，同时强调作为指针的作用，就不难为什么这三种互斥情况分别对应的不同的赋值了。

以'bbbab'为例，去掉基准后，以对应行数、对应列数，对应的动态规划表为： 现在可以开始编写程序了。可以用动态数组的方法降低空间开销，不过没有必要，这个问题的重点在于找到状态与状态转移方程。如果要给出最长回文子序列的具体值，要么考虑回溯算法，要么记录每一次状态转移系三种情况中的哪一种，求出最大长度后再逆着寻找究竟是哪些字符构成了最长回文子序列。

同时，注意到且时有，这里决定了循环的顺序：首先从下往上逐行遍历，再在每一行中从左向右逐个遍历非平凡的字符。这也是为什么基准问题的解是的原因。

# 输入参数
seq = 'bbbab'

class Seq:
    # 最长回文子序列
    def lps_seq(self, seq):
        N = len(seq)
        dp = [[0]*(N+1) for _ in range(N+1)]
        
        for i in range(N, 0, -1):
            dp[i][i-1] = 1
            print(i)
            for j in range(i, N):
                dp[i][j] = dp[i+1][j-1] + 2 if seq[i-1] == seq[j] else max(dp[i+1][j], dp[i][j-1])
        print(dp, '\n')
        return max(map(max, dp))  # np.max(dp)

lps = Seq()
print(lps.lps_seq(seq))

该算法的时间复杂度与空间复杂度均为，可以通过动态数组的办法轻松地将空间复杂度降至。

输出：

[[0, 0, 0, 0, 0, 0],
 [1, 2, 3, 3, 4, 0],
 [0, 1, 2, 2, 3, 0],
 [0, 0, 1, 1, 3, 0],
 [0, 0, 0, 1, 1, 0],
 [0, 0, 0, 0, 1, 0]]


4

最长回文子串

其实最长回文子序列问题中对状态定义的思路源自于本问题。本问题比最长回文子序列简单，但状态的定义是类似的，而本问题的状态定义更容易想到，所以实际上应该先讨论本问题，再讨论最长回文子序列问题。记号的含义同最长回文子序列问题中的定义。

最长回文子串问题（the longest palindromic substring，LPS），相较于最长回文子序列问题更为简单，一个直观的思路是利用双指针，使用中心扩展的方式寻找回文子串。当然，也可以使用大名鼎鼎的针对性算法：Manacher算法，时间复杂度为。除了动态规划以外，这些方法都可以在LeetCode 第 5 题：最长回文子串（超详细的解法！！！）中找到。通常而言这些方法会比基本的动态规划更高效，不过为熟悉动态规划，用动态规划的方法解决这个问题也是很有意义的。

在最长回文子序列问题中，我们想到用一个二维数组表示以为开头并以为结尾的子串的最长回文子序列长度——这样定义的灵感来自于中心扩展中的双指针，我们用指针指向子串的开头并用指针指向子串的结尾，如果这一子串为回文串，则及记为子串的长度，否则为。

如果还是感觉没有思绪，可以先分析回文子串的特征：回文子串也是一个子串，在原字符串seq中是连续的，只用一个指针并定义状态为以结尾的最长回文子串并不合适，因为与公共子序列、递增子序列等问题不同的是，这些问题中通常目标子串是随着搜索的进行逐渐从末位插入元素的，前缀并不会改变，所以只需要一个指针指向搜索位置、也就是子串末尾即可；而在最长回文子串问题中，随着指针右移，即使每次右移都能发现当前指向一个回文子串的末位，这些回文子串的前缀通常也是不相同的，前缀同时会随着搜索的进行从首位插入字符，所以想到需要用两个指针将子串“框住”，构造一个二维数组。

明确了状态的定义，接下来找出状态转移就好了。 最长回文子串问题中指针的状态转移比最长回文子序列中的要来的容易，因为子串必须是连续的，而子序列则可以是间断的，只要保持序关系即可。不难分析出， 可见，最长回文子序列问题中的状态转移方程可以被视为本问题中状态转移方程的条件增强版本。由于在状态转移中涉及，令对应行数、对应列数，同时补充定义，并且表的计算应从下至上、从左往右进行： 现在可以开始编写程序了。同样地可以使用动态数组的办法优化空间复杂度，不过并非必要。这里只算出长度，如果需要所有最长回文子串的具体值，只需要找到表中最大的值，并记录对应最大值的指针即可，指向一个最长回文子串的开头，指向最长回文子串的结尾。不过由于对进行了补充定义，坐标等于指针，这一点需要注意。

# 输入参数
seq = 'ACBAABCACBACA'

class Seq:
    # 最长回文子串
    def lps_str(self, seq):
        N = len(seq)
        dp = [[0]*(N+1) for _ in range(N+1)]
        
        for i in range(N, 0, -1):
            dp[i][i-1] = 1
            for j in range(i, N):
                if seq[i-1] == seq[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
        print(dp, '\n')

        return max(map(max, dp))  # np.max(dp)

lps = Seq()
print(lps.lps_str(seq))

该算法的时间复杂度与空间复杂度均为，可以通过动态数组的办法轻松地将空间复杂度降至。

输出：

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 2, 2, 0, 0, 8, 0, 0, 2, 0, 4, 0],
 [0, 1, 0, 0, 0, 0, 6, 0, 2, 0, 0, 2, 0, 0],
 [0, 0, 1, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0],
 [0, 0, 0, 1, 2, 0, 0, 2, 0, 0, 2, 0, 2, 0],
 [0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 7, 0, 2, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 4, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 4, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]




8

最长匹配子列杂例

暂略，有空了再整理

• 一些本文没有提到的序列问题：【算法专题】动态规划之子序列问题

KMP算法

常用于字符串模式匹配的算法有很多，例如BM算法、Horspool算法、Sunday算法、KMP算法、KR算法与AC自动机算法，这里讨论基于动态规划的KMP算法——这是动态规划的一个较难的应用。

《数据结构》严蔚敏著：串的模式匹配通常指子串的定位操作，是各种串处理系统中最重要得到操作之一。

在模式匹配中，称定位操作的对象为主串，记长度为，称需要被定位的串为模式串，记长度为。要定位子串，一个自然的想法是遍历主串的每一个元素，当在所选取主串的第一个字符与模式第一个字符相同时，判断主串第一个字符的下一个字符是否与模式第二个字符相同，如果相同则称匹配成功、继续判断主串第一个字符的下下一个字符是否与模式第二个字符相同……直到在某次结果返回结果“不相同”（称为匹配不成功）时，回溯到主串的第二个字符，继续开始执行判断是否与模式第一个字符相同……循环往复直到遍历主串，或在某趟匹配时匹配到模式的最后一位字符时结果返回匹配成功，返回匹配串的起始下标。实现时，可以用两个计数指针分别表示主串与模式的中当前比较字符的位置，回溯时回溯指针为即可，置。这个算法被称为BF算法，是最简单也最“暴力”的模式匹配苏案发。

BF算法直观、易理解，且处理文本匹配这类问题时有着的近似时间复杂度，但对于01串匹配等问题时却经常出现最坏情况的时间复杂度，而KMP算法是一种比BF算法更好的模式匹配算法，下面推导KMP算法。

模式匹配原理与流程

KMP算法于1977年由Donald E. Knuth，James H. Morris与Vaughan R. Pratt在论文《Fast Pattern Matching in Strings》中首次提出。KMP算法相较于BF算法的改进在于，在每一趟匹配过程中当出现返回结果匹配不成功（称为“失配”）的情况时，值，而是利用这趟匹配最终出现匹配不成功前已匹配成功的结果，在选择下一个进行匹配的主串中字符时 ，选择尽可能靠后的字符，这样就可以跳过不必进行的匹配。而确定具体该选择主串中哪个字符作为下一个进行匹配的字符的过程，这背后蕴含的实际上是一个动态规划的过程。

在初学时我也因为教科书上一堆抽象的数学公式而完全不能理解（即使我是半个数学系毕业的……），现在我希望从需求出发自然地引出前缀表、数组，并探究如何计算整个数组。

让我们先来模拟一个流程，说明为什么最初的算法效率低下，而KMP算法又需要从哪里对最初的算法进行改进，并且改进后指针不会回溯的原因。记主串的长度为、状态串的长度为。

举一个具体的例子，设主串为'ABBBAAAAAAABBBA'、模式串为'AAAABBB'。一趟匹配定义为从上一轮匹配发生失配后的初始化到本轮匹配发生失配的过程，假设在某趟匹配开始时，，： 在BF算法中，由于此时，所以匹配成功，继续匹配，因此i++、j++。这里就不重复匹配成功情况下的过程了，我们观察到当时会出现失配现象而导致这趟匹配终止，让我们从这里继续： 在BF算法中，这时应当回溯指针为，在我们的例子中，，也可以看作回溯到在这趟匹配开始时的并进行i++操作，而则被重新赋为，然后再重新开始下一趟匹配。初始化后如下图所示，注意这里为方便表示匹配、将一趟匹配开始时对比的字符与对准，将随着的i++操作整体向右移了一位。 然而，这样就产生了一些不必要的重复匹配，可以看出其实从到的字符均为'A'，而到的字符也均为'A'，所以其实不必赋，因为在上一趟匹配的结果中已经蕴含了下一趟匹配中前若干次字符匹配必然返回匹配成功。这个例子很好地说明了实际上不必回溯，而也不需要在每趟匹配开始时赋——可以利用到上一趟匹配结果这一BF算法并未利用的信息，跳过一些BF算法中的重复匹配，这就是KMP算法的核心思路。

---

那么KMP算法会怎么做呢？KMP算法中的指针不会回溯，会随着匹配的进行指向下一对匹配字符，这个操作可以通过对分别自增一完成，或者说更新i++、j++，直到发生失配。直到这一步，KMP算法与BF算法还没有太大差别。

利用后文中的数组，这种情况等价于

发生失配后，仍指向下一个字符（而不会回溯），而则会通过某种方式，直接指向当i++时模式中有必要从某处开始匹配的位置——被新赋的值会比更小，被更新后状态的位于前的字符则是没必要参与匹配的，因为当指向就意味着我们已经通过上一趟匹配知道了以前的字符不可能匹配失败，从而避开了重复比对。为保持指向的字符位于同一列，这里将状态右移两位，最终得到下图。 这部分就是KMP算法有别于BF算法的处理，我们现在的目标就是找到如何寻找在每趟匹配开始时的初始化值，所以先从仅有的信息开始——与在上一趟匹配中的结构关系。

---

知道了要解决的问题，就可以来一步步分析了。记主串长为、模式串长为，假设在上一趟匹配中发生了失配且匹配失败前正在匹配的字符为与，同时令、分别表示上一趟匹配开始时的初的始化值，则从与开始直至与以前的字符一定是均返回匹配成功的，否则在与及其后、与以前的某一对字符返回匹配失败时就已经发生了失配并结束上一趟匹配，而不会等到匹配与才失配。

从与开始直至与之前的字符全部返回匹配成功，意味着，也就是说 所以要研究与在上一趟匹配中的关系并尝试由此找到在下一趟匹配的初始化值，只需要研究的结构即可，这是因为从到就包含了上一趟匹配中匹配成功的字符的全部信息。

既然只需要研究状态的结构，我们这里更换一个更典型的模式的例子。在新的例子中，模式为ABBABAB，暂时不必考虑与整个主串的具体值。设在时发生失配： 我们发现且有，这意味着当指针自增一后（即），有

利用后文中的数组，这种情况等价于但

所以令即可，也就是（后文中会提到，其实是），这是因为从上文的推导中可以看出，当指针自增一后，包括在内起向前数的三个字符与的前三个字符均是相匹配的，所以我们不需要令重新将每一对字符都匹配一遍，只要从未知是否相匹配的字符开始匹配就好。KMP算法就是通过这样的办法，避免的回溯（）与重复匹配（通过对的动态初始化）的。不难分析出，本例中状态右移的距离就等于的长度加再减去本趟匹配开始前的初始化值，在这里为。 尽管上图中的对应了与中的子串，但实际上位于末位的是我们单独判断的，而只有是从上一趟匹配的结果中推导出来的。由式知，上图中的可以替换为，在不考虑子串末位字符的情况下（换言之，只考虑能从上一趟匹配中推导出关系的字符），记对应匹配中的主串但位于之前子串、对应匹配中的状态但位于之前子串，易见有，则上图也可以只用的子串与表示。因为且均为的子串，因此本质上是只用到了状态——这是一个主串为、模式串也为的模式匹配问题，特地区分只是为了方便表示到底是哪个子串在进行右移，图示如下： 现在我们来把上述分析的过程抽象一下，从特殊问题推广至一般问题。实际上，上文中的被称为ABBABAB的最长相同前后缀，我们先来看看前缀与后缀的定义。

对于一个字符串str，以'BABAABA'为例，他的前缀（prefix）是不包括末位字符的所有以其首位字符为起始的子串所组成的集合，他的后缀（postfix）是不包括首位字符的所有以其末位字符为终点的子串所组成的集合。对于'BABAABA'而言，他的前缀与后缀为： 接下来我们从这些前缀与后缀中找出所有相同的前后缀，容易想到只需要将长度相同的前缀与后缀进行对比就好了，因为长度不一样的前缀与后缀必然不相同。根据上表不难找出所有的相同的前后缀，在这个例子中只有'BA'是相同的前后缀，自然也是最长的相同前后缀，其长度为。

通过以上定义，可以知道：前文中我们所观察到的“”，实际上就是状态前个字符构成的子串'ABBAB'的一个相同前后缀，而且其恰好是最长的相同前后缀： 所以，只要知道了状态的前个字符构成的子串的最长相同前后缀的长度就可以完成更新的全部流程，记为，其中，而并不需要具体的最长相同前后缀。该值只与有关，而与无关。注意，必然为，因为只有一个字符的字符串的前缀与后缀均为空集，这是由前缀的定义不能包含末位元素与后缀的定义不能包含首位元素所决定的，所以最长相同前后缀的长度当然也为，即不存在。特别地，当中的字符均互不相同时，。

数组被称为前缀表，前缀表及其一些衍生数组也被称为数组或函数数组，这里我们将数组定义为前缀表，并在后文中以数组称呼前缀表。表示前缀表中第位的值。由于数组只与有关，因此可以先将数组计算出来，在匹配的过程中直接使用。

数组可以由动态规划高效计算，在引出KMP算法的流程后再来深入讨论数组的计算。

接下来讨论在更普遍问题中应被初始化为何值及其原因。由于在失配前的匹配均是成功的，所以失配前被匹配的子串等于被匹配的子串，即式，而式又告诉我们，如果在失配前所匹配的子串存在相同前后缀，则意味着此时的后缀 = 的前缀 = 参与匹配子串的前缀 = 参与匹配子串的后缀。在上一轮匹配失配前，指针分别指向参与匹配子串的后缀末位与的后缀末位，现在将上一趟匹配失配前参与匹配子串的后缀当作本趟匹配开始时参与匹配子串的前缀、将上一趟匹配失配前的后缀视为本趟匹配开始时的前缀，根据等式“的后缀 = 的前缀 = 参与匹配子串的前缀 = 参与匹配子串的后缀”，在本趟匹配开始时参与匹配子串的前缀与的前缀是处处相等的——因为他们对应的前缀子串在上一趟匹配中其实就已经作为后缀被匹配过了，这时只需要对比本趟匹配开始时参与匹配的前缀的下一位即可，所以指针、是一对可行的初始化值。在图像上的表现为将右移至中对于后缀之处。

当，为什么可行的初始化同时也是所有可能的更新值中的最大者呢？在前文的分析中，只有存在相同前后缀时才可能避开对相同前缀与后缀的重复匹配，并尽可能使初始化为最大的值。根据推导，对于一个长为的相同前后缀，则；而正是最大的可能的，所以就是——尽可能初始化为最大的值。不可能在任何情况下都存在且能保证匹配中的不重不漏。

总结：当：i++，。

• 为什么令而不是？之所以令而不是，是因为我们利用的是失配前的那些匹配成功的信息。对于很多模式匹配问题，主串与状态的字符集中都不止两种字符，这种情况下如果发生失配，则我们不可能仅从失配时的推断出与的具体值与他们同中其他字符的关系，除非回到主串与模式串中进行查找与比对。所以我们在寻找如何最大初始化的过程中，其实对信息的利用主要都是从上一位开始向首位进行的。

---

对于模式为ABBABAB的例子，上文中只分析了的情况，可如果，也就是说呢？不妨将例子中的与更改为'A'，构造一种的情况，如下图所示： 计算后得知仍为，但，这时若仍令i++、，会发现 如果这样操作是合理的，那么当前正匹配的字符串为与，但——可如果，那么在这里就应该失配了，又怎么去讨论是否等于呢？因为无论是等于还是不等于，在前一位就已经发生失配了，那么这一趟匹配绝无可能正确地匹配到整个模式，而我们从与开始匹配时就已经默认了、与，这与事实背道而驰。

究其根本，发生这种错误的根本原因是因为我们应该在匹配前进行某种操作，保证有，否则就有可能出现这样的问题。为什么我们确定需要通过将初始化为其他的值以期解决问题？因为总会随着匹配的进行自而增一，故只能从入手。

先暂时回到的情况，我们为什么会考虑初始化呢？是因为是的前个字符构成的子串的最长相同前后缀的长度，记为。既然赋为的前个字符构成的子串的最长相同前后缀的长度不可行，那么我们就应该转而寻找第二长的相同前后缀的长度，此时第二长的相同前后缀的长度才有可能对应最大可行的，记为，再继续判断是否可行，即是否有，如果成立则赋，否则继续寻找第三长的相同前后缀的长度，记为，判断是否可行、是否有，如果成立则赋，否则继续寻找第四长的相同前后缀的长度……直到某次有成立、赋，或直到时也无法更新，这时回到了类似BF算法的情景，应赋。

到这里，在已知数组的情况下就可以写出KMP算法的匹配代码了。

# strings = 'AGCATAATAATTAA'
# T = 'ATAATA'

next = [0, 0, 1, 1, 2, 3]
    
def kmp(strings, T, loc=0):
    S = strings[loc:]
    n = len(S)
    m = len(T)
    j = 0
        
    for i in range(n):
        while j and S[i] != T[j]:
            j = next[j-1]
        if S[i] == T[j]:
            j += 1
        if j == m:
            return i
    return -1

前缀表的动态规划

现在让我们讨论怎么快速地计算数组吧。注意到“就是的前个字符组成的子串的最长相同前后缀的长度”中的关键词：“最长”、“前后缀”、“长度”，这意味着我们或许可以像前文中在最长公共子串问题中的分析那样，用动态规划方法高效求解——只不过加上“纳入考虑的公共子串必须同时也是两字符串的前后缀”的条件限制。

按这类问题动态规划的“套路”，定义状态等于、也等于，注意到实际上表示的前个字符所组成的子串的最长相同前后缀之长度，这是一个重要信息，所以计算不仅是一个动态规划问题，也是一个模式匹配问题，且主串与状态串均为。又观察知对应的最长相同前后缀相较于对应的最长相同前后缀均在末位新增了一个字符，且新增的字符分别为与，我们需要讨论这两个字符以找到状态转移；同时，假设已知，则根据已知的，有 下面进行状态转移分析：

• 当，意味着 可见代表的最长相同前后缀长度一定恰比大一，所以有。

• 当，记所对应的式等号左边的前缀为、等号右边的后缀为，则与在中的排列为：

  注意，当 足够长， 是有可能位于左边的

  现分析对应的最长相同前后缀的情况：

  • 对于前缀，如果存在，其中且，则一定有 可见与中的较小值对应的一定是较大值对应的前缀，并且可以确认这一前缀是几级前缀，除非，则两个相等，互为子串（因为前缀不包括最后一个元素，所以这时不能说是前缀）。

  • 前提同上，但后缀与间就不存在这样的关系。 如果不利用找出两个后缀具体的值并通过模式匹配对字符逐个比对，这时根本无法找出二者更进一步的对应关系，他们也有可能完全不同，也有可能部分相同，还有可能完全相同，而且即使部分相同，也找不出所有相同字符在与中的位置。

  所以不能通过具体的前后缀寻找，因为的实现中只记录了的长度为的子串的最长相同前后缀的长度，但并没有具体找出并记录这些最长相同前后缀的具体值，根据上文中对与相应最长相同前后缀关系的分析，我们无法近通过长度找到与对应最长相同前后缀的关系 我们无法通过已知的找出所有具体的与，再根据他们找出对应的最长相同前后缀与，从而计算出。

  既然最直观的想法——计算出所有具体的与并根据他们与、的关系找到、的办法行不通，则只能考虑从本身入手。仔细分析后发现，实际上我们也并不需要所有具体的与，我们首先只需要的长度为且满足的子串并找到该子串的最长相同前后缀长度——这里解释一下为什么需要该子串满足这两点要求，这是计算最核心的一点。究其根本，是因为对应子串的前后缀要成为最长相同前后缀，首先必须满足前缀的前个字符与对应的后缀前个字符必须是全部匹配成功（前个对应位置的字符应全部相同，保证除最后一个字符外二者是相同公共前后缀）的、同时后缀的前个字符组成的子串必须是的后缀（该要求源自于在的大前提下可以推导出一定不大于，而不能作为的最长前缀只是因为，所以这样限制就可以保证要找的后缀有可能且是仅有可能的成为最大前缀的字符串）。记是某个小于的非负整数、表示除开最后一位字符外的相同前后缀长度，则只需要找出满足下式的，于是就是符合前述限制的相同前后缀的长度： 在具体的计算过程中，注意到正是满足条件的最大的——的长度为且满足的子串的最长相同前后缀长度，记为，也就是的前个字符所组成的子串的最长相同前后缀之长度，

  • 当，先赋，然后判断是否有成立，若等式成立则赋值，若等式不成立则寻找满足式的第二大的，记为
  • 类似对的分析，这时实际上正是的长度为且满足的子串的最长相同前后缀长度，根据结果再次判断是否有成立，如果成立则赋值，等式不成立则寻找满足式的第三大的，记为
  • 令，判断是否有成立，若成立则赋值，不成立则寻找满足式的第四大的，记为
  • … …
  • 直到在时第一次有成立、令，这时无需再判断是否有成立，或直到判断到最小的，记为，仍没有成立，说明不存在公共前后缀，视最长公共前后缀长度为，这时赋。

  以上就是状态转移的具体描述了。为什么说、、等，而不说、、等等呢？原因和第二、三、四点中对的分析类似，因为在匹配不成功时导致匹配不成功的这对字符我们没有也没有必要讨论他们具体值，因为在实际问题中字符集可能很大，我们只要知道他俩不相等即可（所以将他俩排除，“不相等”难以被利用），最关键的信息来自于这对字符之前那些相等的字符们，故只考虑匹配不成功字符以前的字符，他们的长度为减一。

  综上所述，现在可以按分析编写计算数组的程序了。其实可以被放入循环中进行判断，也就是说其实可以将所有的判断均放入循环之中，这包括了第一步对的判断，令即可。

  T = 'abaabcac'
  m = len(T)
  next = [0 for _ in range(m)]
  
  for j in range(1, m):  # j+1为T正在匹配字符的位置，T[j]为最长后缀尾部
      y = next[j-1]  # 初始化y为next[j-1]，next[j-1]+1是next[j]可能的最大值；T[y]为最长前缀尾部
      while y > 0 and T[y] != T[j]:  # 若满足条件则next[j]向左滑，y被更新为所有y中第n大的y
          y = next[y-1]  # 左滑的过程同时也是状态转移的过程，有next[next[next[...next[y-1]]]]
      if T[y] == T[j]:
          y += 1  # 除了y <= 0，结果均加1，因为另外两种情况都有T[y] == T[j]，需要加1才能得到正确结果
      next[j] = y
  
  print(next)

  输出：

  [0, 0, 1, 1, 2, 0, 1, 0]

补充KMP算法可视化：KMP 学一遍忘一遍？ACM 金牌选手用可视化直击本质，理解了内核后想忘记都难！

基本的实现

在实际的实现中，输入参数除了需要匹配的字符串与模式以外，增加一个参数，将由从第个字符起始直到最后一个字符构成的子串作为主串，因为根据前文的分析，我们只返回了第一个匹配到的字符串的起始下标，所以这样定义的好处是进行多轮KMP算法以找出所有的匹配字符串下标时，将上一轮KMP算法返回的下标减去的长度加一后作为本轮KMP算法的即可。

# 输入参数
strings = 'AGCATAATAATTAA'
T = 'ATAATA'

class Algorithm:
    def perfix(