二三事

“みんなみんな大好き！”

0%

动态规划算法

Posted on Edited on In
　　搜集了若干我感兴趣的DP问题，包括背包问题、最长匹配子列与扰乱字符串等若干问题。囊括了一些DP的应用，例如KMP算法、Dijkstra算法等。还涉及了一些DP的优化手段与DP的进阶应用，例如单调队列与插头DP。
　　文章会很长哦，可以看作是我对各DP问题学习与研究的详细笔记😌

动态规划

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
目录：
├───动态规划
│
├───背包模型
|   ├───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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 输入参数
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)

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

1
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]]
1
print(dpMatrix[-1][-1])

输出：

8

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

完全背包

# 也可以定义一维状态

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

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

状态转移方程为

且若，则

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 输入参数
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)

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

1
print(dpMatrix)

输出：

[[0, 0,  0,  0,  0],
 [0, 15, 30, 45, 60], 
 [0, 15, 30, 45, 60], 
 [0, 15, 30, 45, 60]]
1
print(dpMatrix[-1][-1 ])

输出：

60

滚动数组优化空间复杂度

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 输入参数
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 输入参数
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——除非两个参数均为，这意味着背包未被填满、值为的情况被视为无效数据）。根据状态转移方程，由于都是由计算而来，因此只需要改变初始化条件就可以让算法仅在恰装满背包时取有效数据，否则值为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 输入参数
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
1
2
3
4
5
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 输入参数
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

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

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

按上述分析，有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 二维数组的最大值
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])

最少硬币组合

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

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

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

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

1
2
3
4
5
6
7
8
9
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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# 输入参数
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就需要改为记录当前的值，而不能只赋。以下代码引用自中等题：最优硬币组合问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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背包模型：

  • 力扣 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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 输入参数
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 输入参数
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 输入参数
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稍加改动，就可以得到不同的最长递减子序列（改为）、最长严格递增子序列（改为）、最长等差子序列等等。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 输入参数
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 输入参数
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 输入参数
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算法再次解决这个问题。现在可以开始编写程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 输入参数
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++的实现可以参考双指针滑动窗口、动态规划、暴力线性遍历，可以做到线性时间复杂度。

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

1
2
3
4
5
6
7
8
9
10
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. 判断复杂度：需要考虑具体的实现方式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 输入参数
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'为例，去掉基准后，以对应行数、对应列数，对应的动态规划表为： 现在可以开始编写程序了。可以用动态数组的方法降低空间开销，不过没有必要，这个问题的重点在于找到状态与状态转移方程。如果要给出最长回文子序列的具体值，要么考虑回溯算法，要么记录每一次状态转移系三种情况中的哪一种，求出最大长度后再逆着寻找究竟是哪些字符构成了最长回文子序列。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 输入参数
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中是连续的，只用一个指针并定义状态为以结尾的最长回文子串并不合适，因为与公共子序列、递增子序列等问题不同的是，这些问题中通常目标子串是随着搜索的进行逐渐从末位插入元素的，前缀并不会改变，所以只需要一个指针指向搜索位置、也就是子串末尾即可；而在最长回文子串问题中，随着指针右移，即使每次右移都能发现当前指向一个回文子串的末位，这些回文子串的前缀通常也是不相同的，前缀同时会随着搜索的进行从首位插入字符，所以想到需要用两个指针将子串“框住”，构造一个二维数组。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 输入参数
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算法的匹配代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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

前缀表的动态规划

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

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

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

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

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

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

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

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

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

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

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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算法的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 输入参数
strings = 'AGCATAATAATTAA'
T = 'ATAATA'

class Algorithm:
    def perfix(self, T):
        m = len(T)
        p = [0 for _ in range(m)]
        
        for j in range(1, m):
            y = p[j-1]
            while y > 0 and T[y] != T[j]:
                y = p[y-1]
            if T[y] == T[j]:
                y += 1
            p[j] = y
            
        return p
    
    # 模式匹配KMP算法
    def kmp(self, strings, T, loc=0):
        S = strings[loc:]
        next = self.perfix(T)
        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
            
kmp = Algorithm()
print(kmp.kmp(strings, T))

输出：

8

其中计算数组的时间复杂度为，遍历的时间复杂度为，所以KMP算法的时间复杂度为（由于，所以说也没问题）；如果允许原地修改则空间复杂度为，在我们的实现中空间复杂度为。

常数优化与nextval改进

暂略

最长重复子串之二

暂略

Kadane算法

Kadane算法是动态规划的一个经典应用，用以求解最大子数组和问题（maximum subarray problem）。这类问题的描述通常为：给定一组整数数组（可以取负值），找出一个连续子数组，使得其元素之和是所有子数组中的最大者。

最大子数组和问题最早由Ulf Grenander于1977提出并同时给出了一个极大似然估计的简化模型，Jay Kadane在卡内基梅隆大学的一次研讨会上听闻了该问题的一维形式，随后在一分钟内设计出了时间复杂度为的算法，现在我们称该算法为Kadane算法。这是理论最低时间复杂度的算法，1982年David Gries应用Dijkstra算法也得到了一个时间复杂度为的算法。

原理与实现

作为动态规划的应用，Kadane算法首先类似最长匹配子列问题定义了指针指向连续子数组的末位，并记表示在当前位置（第位）结束的最大子数组和，以一个变量存储当前已知的最大子数组和。当迭代结束，该变量内存储的值即为全局最大子数组和。

现在只需要找到状态转移方程，就可以实现算法了。设给定的长度为的整数数组为nums，为方便说明原理，定义一个不需要实现的假想指针指向当前最大子数组和所对应的子数组的起始位置。

  • 如果，显然有，此时不变，子数组长度加一；
  • 但如果，则比较与：
    • 若更大，则被插入子数组，此时仍不变，子数组长度加一；
    • 若更大，则子数组应该从处重新开始搜寻，此时指向，子数组长度重置为一。

分析以上逻辑，实际上不需要讨论的正负，可以将这一步并入与大小的比较，结果相同。因此，简化后的流程就是这一动态规划过程的状态转移方程： 同时用变量dp_maximum记录当前已知的最大子数组和： 初始化时，令。同时注意到状态转移方程中计算当前状态至多会用到前一位的状态，说明可我们以使用滚动数组的方法，做到常数级别的空间复杂度。

Kadane算法就是这样一个简单但高效的动态规划应用，现在可以开始编写程序了。

1
2
3
4
5
6
7
8
9
class Algorithm:
    # Kadane算法(最大子数组和)
    def kadane(self, nums):
        dp = nums[0]
        dp_maximum = nums[0]
        for n in range(1, len(nums)):
            dp = max(nums[n], dp+nums[n])
            dp_maximum = max(dp, dp_maximum)
        return dp_maximum

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

如果要计算最小子数组和，则将代码中的max改为min即可。

最大环形子数组和

环形数组可被视为一个有限群。环形数组的特点是它的末端和开头相连，形式上 的下一个元素是circular[(i + 1) % n]，而 的前一个元素是circular[(i - 1 + n) % n]。现在需要计算环形数组的最大子数组和。环形子数组要求不可重复，即对于子数组，不存在、，使得。

最大环形子数组和问题一般被视为最大子数组和的衍生问题。最大和的环形子数组要么没有越过的最后一位，这时最大和的环形子数组与最大和的子数组相同，和也相同；要么越过了的最后一位，这时最大环形子数组和与最大子数组和不同。为方便表示环形子数组是否越过的最后一位，我们将两个相连，表示为 # 提醒，我们不会直接在两个相连的上直接使用Kadane算法，因为这样操作所得到的结果对应的子数组可能并不满足定义“环形子数组不可重复”而导致其（相对于来说）并不是一个环形子数组。所以，不可以将视为使两个相连的子数组和最大化的子数组，而应该强调只是一个的环形子数组，只不过是使环形子数组和最大化的特殊环形子数组。

  1. 如果没有越过的最后一位，则可被示意为 第二个是不必要的，用一个表示即为 这时可以被视为一个普通的子数组。

  2. 如果越过了的最后一位，则可被示意为 然而，这一情况其实可以被转化为第一种情况。如果我们尝试把环形子数组表示在一个里，分别记原本环形子数组在第一个中的部分为、第二个中的部分为，由于环形子数组要求不可重复，所以与必不相交，故可以将环形子数组示意为 可以发现，除了子数组、以外，中还余下了一部分子数组，记为。如果观察细致，可以发现实际上是的最小子数组和对应的子数组，因为与分别为的前缀子数组与后缀子数组，以函数表示数组的和，即，有 其中是一个确定的常数，由于（这里表示拼接操作，取单词string的动词含义而非名词！），因此，意味着我们在计算以最大化环形子数组和的同时，也在最大化前缀子数组和加上后缀子数组和，此时最小化。按照定义，正是的最小子数组和。

    这种情况下，取即可。

综上分析，为求出最大环形子数组和，新算法可按如下步骤执行：

  1. 对应用Kadane算法，计算出最大子数组和与最小子数组和；
  2. 判断是否有越过的最后一位，
    • 如果是，返回数组和减去最小子数组和的差；
    • 如果否，返回最大子数组和。

实际上，我们并不需要判断条件是否有越过的最后一位（尽管利用始位指针并保存恰取最大子数组和时的末位指针可以实现这一点），然后再根据条件返回结果。多数情况下我们可以直接取最大子数组和与数组和减去最小子数组和的差之间的最大值作为结果，但仅限于多数情况，现在我们需要讨论为什么多数情况下可以取两者的最大值作为返回值，以及对那些少数情况该怎么办。

为方便讨论，记最大子数组和为、数组和减去最小子数组和的差为。实际上完全等价于环形子数组在限制条件不可越过末位下的最大和（由Kadane算法所保证），但却并不总是等价于环形子数组在限制条件必须越过末位下的最大和，仅在最大和环形子数组越过末位时，才能代表环形子数组在限制条件必须越过末位下的最大和。如果能代表环形子数组在限制条件不可越过末位下的最大和、能代表环形子数组在限制条件必须越过末位下的最大和，则直接返回是没有问题的，因为所有的环形子数组要么越过末位、要么不越过末位，取背后的逻辑是：这一情况下，我们把所有的环形子数组分为了不相交的两类，其中一类数组和的最大值为，另一类数组和的最大值为，那么当然就是所有环形子数组和的最大值。

然而，以上结论只在能够代表越过末位的环形子数组的子数组和最大值时成立，即与均非空时。一旦，则存在一个从到的双射，由于环形数组的性质，或者更本质地讲是由于有限群的性质，导致这时

  • 有，不再表示越过末位的环形子数组的子数组和最大值，；
  • 记为实际的越过末位的环形子数组的子数组和最大值，则。

所以，面对这一情况，直接返回即可；这时返回是不可行的，因为已经失去了任何意义，。回到前提进行推理，也不难发现当且仅当在中的数字均非正时才有可能发生，而后者又等价于“”这一命题。

如果读者正式学过群论，以上推导是很容易理解的。

综上所述，我们只需要在时返回，其余情况下直接返回即可，并不需要额外实现判断是否越过了最后一位的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Algorithm:
    # 最大环形子数组和
    def maximumSumCircularSubarray(self, nums):
        max1 = nums[0]
        max2 = nums[0]
        min1 = nums[0]
        min2 = nums[0]
        whole = nums[0]
        for n in range(1, len(nums)):
            max1 = max(nums[n], max1+nums[n])
            min1 = min(nums[n], min1+nums[n])
            max2 = max(max1, max2)
            min2 = min(min1, min2)
            whole += nums[n]

        # 如果返回max2与min2，就等价于Kadane算法分别返回了最大子数组和与最小子数组和
        if whole == min2:
            return max2
        return max(max2, whole-min2)

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

组合优化Others

活动选择

活动选择问题（activity-selection problem）是一个十分经典的贪心算法代表性问题。然而，几乎每一个贪心算法都对应一个更繁琐的动态规划算法，所以这里将用动态规划的方式解决这个问题。

活动选择问题是指，假设一共有个可安排的活动，这些活动有着相应的开始时间与结束时间。由于场地的限制，在同一时间只能举办一项活动，也就是说如果有两个活动均被选中，设的活动举办时间为、的活动举办时间为（为开始时间、为结束时间），那么对而言应有，这时称是兼容的，否则称为不兼容。现在，我们希望选出一个包含活动最多的最大兼容活动集。

例如，对下面个可安排活动找出最大兼容活动集： 在《Introduction to Algorithms》一书中，作者从最优子结构的证明过程中找出了状态转移：设为一个从第个活动结束到第个活动开始时间段内的最大兼容活动集，假定包含活动。由于最优解包含，则得到了两个子问题：寻找与。我们有，所以这时，接着“剪切 - 粘贴”、也就是用反证法证明最优解必然包含两个子问题的最优解。

证明过程实际上就构造出了状态转移，设，由于我们并不知道究竟哪些活动属于最优解，所以只能遍历之间的所有活动，最后取的最大值。贪心算法则不会在这里进行遍历以寻找最优解中的元素，而是直接选择在结束后开始而最早结束的活动。 在用这一状态转移方程编写程序时，务必注意应自下而上遍历、则应从左往右遍历，如果想不明白，任取一对的，圈出在表中的位置，原因一目了然，例如对于一张的表，当时所有可能的对应的位置为： 现在可以开始编写程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 输入参数
s = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
f = [4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]

class Solution:
    # 活动选择
    def activitySelection(self, s, f):
        n = len(s)
        dp = [[0]*n for _ in  range(n)]
        i = 0
        j = 0

        for i in range(n-3, -1, -1):
            for j in range(i+2, n):
                dp_max = 0
                for k in range(i+1, j):
                    if s[k] >= f[i] and f[k] <= s[j]:
                        dp_k = dp[i][k] + dp[k][j] + 1
                        if dp_k > dp_max:
                            dp_max = dp_k
                dp[i][j] = dp_max
        print(dp)
        return max(map(max, dp))  # np.max(dp)
            
activity_selection = Solution()
print(activity_selection.activitySelection(s, f))

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

输出： 表中的最大值为np.max(dp)=2，并且存在两个值为的元素，分别为与。注意，由于活动已事先按结束时间排序，故对于而言在与之间最大兼容活动集包含的活动个数为，加上与，实际上在所有活动中考虑的最大兼容活动集包含的活动个数为。对的分析同理，这时说明在与之间最大兼容活动集包含的活动个数为，加上与，实际上的最大兼容活动集包含的活动个数也为。

若还需要给出具体的活动安排，则可以根据结果搜寻开始时间在之后、结束时间在或且互相兼容的两个活动，这样就可以得到两组、也是仅有的两组最大兼容活动集，这是最简单的搜寻方法。

编辑距离

最短编辑距离（edit distance / minimum edit distance）是一个非常之经典的动态规划问题。如果只是初见，可能很难想到这个问题可以通过动态规划的方法解决。最短编辑距离是这样描述的：提供三种针对单词的操作，分别为在单词的某处插入一个字母、删除一个字母与替换一个字母，求通过这三种操作将单词word_1转换为word_2的最少操作次数。

以单词word_1 = 'csgo'与单词word_2 = 'coser'为例，先讨论为什么这可以是一个动态规划问题。通过前面这么多问题的分析，大概也能总结出动态规划的目的：找出状态与状态转移，并通过一些初始条件（基问题）与状态转移，求出整个表，其中表通常是一维或二维的（三维及以上系高维动态规划），并且每个表的值都对应着一个子问题的解。要用动态规划解决最短编辑距离问题，那么直观上表应该是二维的。 现在的问题是如何定义状态、究竟该往中填入什么。由于我们希望套用动态规划的模型，所以定义的状态应当能够统一插入、替换与删除三种操作。不妨先向表中分别填入截止至word_1与word_2的顺序子串，观察他们的规律： 为简化问题，我们取表的一部分进行分析，不妨取表右下角的四个元素，按逐行从左至右的顺序分别记为、、与，如图所示： 或许我们可以令状态为从word_1的前个字符构成的字符串经一系列操作转换为word_2的前个字符构成的字符串所需要的最短操作次数，令表中红色字符为子问题的word_1、紫罗兰色字符为子问题的word_2，这样就可以问题分解为若干子问题。按逐行从左至右的顺序分别设表格单元对应在表的值为、、与，观察上图，以为基准，可以发现：

  • 当两单词末位字符不同时，若对'csgo'进行一次删除末位字符操作，则 ，对应
  • 当两单词末位字符不同时，若对'csgo'在末位插入一个字符，由于我们插入的字符一定是匹配'coser'的，这里应增加'r'，否则需要删除再重新插入，于是在word_1末位插入字符等价于不必考虑'word_2'的末位字符，因此 ，对应
  • 当两单词末位字符不同时，若对'csgo'替换一次末位字符，类似上一种情况，这时可以同时不考虑word_1与word_2，所以 ，对应
  • 在两单词的末位字符相同（尽管这一例子不是这种情况），意味着可以直接“无视”两单词的末位字符，这时不必对末位字符进行任何插入、替换与删除操作，这种情况类似于上一情况（或者说上一情况下进行替换操作后得到了这一情况），但并不需要对操作数加——因为没有进行操作，对应

于是得到了表的递推公式。由于被定义为word_1的前个字符转换至word_2的前个字符的最短操作距离，所以除了初始化的值（简单问题的解 / 基解，在这里是时的状态值），均定义为 综上所述，再考虑初始化的值，现在可以写出状态转移方程了： 现在可以开始编写程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 输入参数
word_1 = 'willugooutwithme'
word_2 = 'iwillalwaysloveu'

class Solution:
    # 编辑距离
    def editDistance(self, word_1, word_2):
        n = len(word_1)
        m = len(word_2)
        dp = [[0]*(m+1) for _ in range(n+1)]
        
        dp[0][0] = 0
        for j in range(1, m+1):
            dp[0][j] = j
        for i in range(1, n+1):
            dp[i][0] = i
        for r in range(1, n+1):  # row
            for c in range(1, m+1):  # column
                dp[r][c] = dp[r-1][c-1] if word_1[r-1] == word_2[c-1] else min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
        return dp[n][m]

        
edit_distance = Solution()
print(edit_distance.editDistance(word_1, word_2))

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

输出：

13

这个算法针对句子等也是可用的，不止能用来比对单词，因为他是按下标进行匹配的。

通配符匹配

通配符匹配（wildcard matching / wildcard pattern matching）也是一个模式匹配问题，输入包含一个长为的主串与一个长为的模式串，需要实现一个支持'?'与'*'匹配规则的通配符匹配。为简化实现，属于通配符集的字符仅可能在中出现。该匹配规则具体描述如下：

  • '?'可以匹配任何单个字符
  • '*'可以匹配任何字符序列，包括空字符序列''

如果完全匹配则返回true，否则返回false。

为了寻找思路，我们先来看一个例子。设S = 'youonlyliveonce'、T = 'y*n*n?e'，对两个字符串逐字符制表，对于匹配成功的记为或；对于匹配不成功的为。 记上表为。可以看出，如果在表中可以找到一条由（或）组成的路径，使得路径从表的左上角出发而最终到达表的右下角时，则完全匹配，返回true；否则返回false。在本例中，由若干所组成的路径就是能够到达表右下角的一条路径，所以应当返回true。

因而，若是希望用动态规划解决这个问题，就需要找出有可能到达表右下角的合法路径在表格之间转移的规则。对于'?'与英文字母的匹配是容易想到的，记当前匹配字符为，对应：

  • 如果中第个字符为通配符'?'，这时无论如何也会匹配成功一位，所以路径向右下方延展一格，即，然后讨论第个字符；
  • 如果中第个字符为小写英语字母，则路径当且仅当时向右下角延展一格，即，并继续讨论第个字符，否则路径中断，不再延展。

不满足以上规则的路径是非法的。难点在于，若的当前匹配字符为'*'、，该如何确定路径的走向以确保其合法且有可能到达表的右下角呢？由于'*'至少可以匹配空字符，所以路径先向下延展一格，此时路径点来到了，新的问题是，在这之后路径该向右延展多少格——也就是'*'应该匹配几个字符。

这时我们发现好像找不到状态转移方程，进而也无法通过动态规划确定'*'应该匹配几个字符——至少我只想得到用回溯算法求解。

我们找不到状态转移的根本原因是如果将定义为表、将表格中的值（逐字符匹配结果）定义为状态，则分解不出子问题。经过这么多个动态规划问题的“洗礼”，这时应敏锐地察觉到，我们应当在逐字符匹配结果的基础上进行一定改造，使问题可以被拆解为子问题、找到递推关系式，例如，可以定义状态为的前个字符组成的子串与的前个字符组成的子串是否完全匹配，若匹配则记为true，否则记为false。这样，每一个都对应了一张不同的表，但我们不关心每一张表内部的路径是怎样的，而只关心他们的结果，并希望由此找到递推关系。

在这样的状态定义下，其他情况的状态转移不言自明，只解释当时的取值问题。我们如此定义状态，最大的好处便是不需要讨论确定'*'到底匹配了几个字符，因为眼下只关注的取值。那么显然地，当只研究时，可以被视为'?...'或''。若将视为'?...'，这时'*'至少匹配了一个字符，则；若将视为''，则。至于与是多少——这就是的子问题的解了，我们会通过基解，利用动态规划逐步得知，当计算到时，这两个值均是已知的。

在这样的定义下，只考虑内容为true的表格，true简记为，则表为： 可见在表中也存在着这样一条路径。相较于表中的路径，表去掉了非法路径（减枝），余下的路径均是向着或右、或下、或右下延展的。这样，只要表右下角的表格中的值为true，就说明完全匹配，否则不完全匹配。就像鲜花一样，左上角是根，右下角则是花朵，这样定义状态使得我们不需要关注是否存在花茎、枝干，只要观察到花蕊在随风摇曳，就说明花儿还是完整地存在着。

不难分析出，每一行的分布只与及上一行的分布有关，状态转移与的情况是类似的： 文字说明：

  • 初始化表的第一列与第一行为false，除了记为true
  • 如果为文本字符，则遍历的字符将与进行匹配，若匹配成功则延续的状态（如果还想不明白，请回到我们对的定义），若整行均为false，说明匹配均失败，程序直接返回最终结果false；并且，匹配可以从第四种情况中定义的下标开始以减少不必要的匹配
  • 如果为通配符'?'，则按上一种情况中一定匹配成功的结果处理，可以通过将整体右移一位快速得到而无需遍历（队列）
  • 如果为通配符'*'，则向下延续上一行中匹配成功的状态true，并在本行对匹配成功的状态true向右延续，具体操作为先找到中第一个为true的对象，记其下标为，则对行下标大于等于的对象均赋值true

对照代码，一目了然：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 输入参数
strings = 'やがて君になる'
T = '*が??*な?'

class Solution:
    # 通配符匹配
    def wildcardMatching(self, strings, T, loc=0):
        S = strings[loc:]
        n = len(S)
        m = len(T)

        dp_1 = [False for _ in range(n+1)]
        dp_2 = [False for _ in range(n+1)]
        dp_1[0] = True

        k = 0  # 记录行的第一个T的下标以处理'*'的情况并减少模式匹配
        k_seq = []
        for i in range(1, m+1):
            if T[i-1] == '*':
                dp_1 = [False]*k + [True]*(n-k+1)
            elif T[i-1] == '?':
                dp_1 = [False] + dp_1  # 队列
                dp_1.pop()
                k += 1
            else:
                for j in range(k+1, n+1):
                    if T[i-1] == S[j-1] and dp_1[j-1] == True:
                        dp_2[j] = True
                        k_seq.append(j)
                if len(k_seq) == 0:
                    return False
                else:
                    k = k_seq[0]
                    k_seq = []
                dp_1 = dp_2
                dp_2 = [False for _ in range(n+1)]

        return dp_1[-1]

wildcard_matching = Solution()
print(wildcard_matching.wildcardMatching(strings, T))

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

输出：

true

执行时间轻松击败力扣上96.60%的人，内存开销击败90.34%的人。虽然这个问题在力扣上属于hard题目，个人认为只要能想到如何定义状态其实就不是难题。

现在来看一个变种问题，正则表达式匹配问题，但额外要求恰完全匹配。借着这个问题，现在套用刚才的思路来完整地分析一遍流程。

本问题的完整描述为，正则完全匹配是指输入包含一个长为的主串与一个长为的模式串，需要实现一个支持'.'与'*'的正则表达式匹配。为简化实现，'.'与'*'仅可能在中出现。具体言之，'.'与'*'的匹配规则为：

  • '.'可以匹配任何单个字符
  • '*'可以匹配零个或多个前面的那个元素

如果完全匹配则返回true，否则返回false。

可以看出，'.'的作用与上一问题中'?'的作用完全相同，我们完全可以仿照上一问题的解决思路，只需要关注如何处理本问题中的'*'即可。照搬通配符匹配问题中我们对状态的定义：为的前个字符组成的子串与的前个字符组成的子串是否完全匹配，若匹配则记为true，否则记为false。

这里还是举一个具体的例子，例如S = 'coooolleepic'、T = 'go**.l.*pic*'，则不难得到其表为： 可见，唯一区别仅仅是当等于'*'时当前行的true不再一直向右延展到底，而是向右延展、直到；如果则需要知道'?'实际上匹配的是何字符，视为该字符。这一区别为本问题的表相较于上一问题具备了一些新的性质：

  • 单调递增
  • 路径不存在 T 字形分叉
  • '*'不被允许位于的首位
  • 不能再将'.*'与'*.'均视为'*'，对于'.*'，要明确'.'具体匹配了什么字符，这样才能知道其后的'*'可能匹配什么重复字符
  • 若，则行中每个表格对应的匹配字符可能是不同的，例如分别匹配了'o'、'o'、'o'、与'l'，但无论搜索进行至哪一行，对于某一确定的行而言，已匹配的字符都是固定的，不会随着搜索的进行而改变，所以需要额外使用一个向量用以存储当时行中值为true处所匹配的字符，用以更新

实际上重新讨论为'*'时的情况即可，的其余情况及初始化按上一问题中的处理方式处理，自起始，不能为'*'，则可以列出状态转移：

  1. 当：

    • 若，

    • 若为其他字符，这时'*'要么匹配空字符、要么匹配，故

    • 若，这时'*'要么匹配空字符、要么匹配'.'所匹配的元素，利用，将这一子问题转化为另一子问题“且为其他字符”，故

  2. 当：将整体右移一格作为，同时记录

  3. 当为其他字符：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    # 正则表达式匹配、完全匹配
    def wildcardMatchingRem(self, strings, T, loc=0):
        S = strings[loc:]
        n = len(S)
        m = len(T)
        dp_1 = [False for _ in range(n+1)]
        dp_2 = [False for _ in range(n+1)]
        dp_1[0] = True
        k = 1
        k_seq = []
        j_set = []

        for i in range(1, m+1):
            if T[i-1] == '*':
                if T[i-2] == '.':
                    dp_1 = [False]*k + [True]*(n-k+1)
                elif T[i-2] != '*':
                    for j in range(k, n+1):
                        a = dp_1[j] or (T[i-2] == S[j-1])
                        if a:
                            dp_2[j] = a
                            k_seq.append(j)
                    dp_1 = dp_2
                    dp_2 = [False for _ in range(n+1)]
                    k = k_seq[0]
                    k_seq = []

            elif T[i-1] == '.':
                dp_1 = [False] + dp_1
                dp_1.pop()
                j_set = dp_1
                k += 1

            else:
                for j in range(k, n+1):
                    a = dp_1[j-1] and (T[i-1] == S[j-1])
                    if a:
                        dp_2[j] = a
                        k_seq.append(j)
                if any(k_seq) == False:
                    return False
                dp_1 = dp_2
                dp_2 = [False for _ in range(n+1)]
                k = k_seq[0]
                k_seq = []

        return dp_1[-1]

复杂度同上。

正则表达式匹配

正则表达式匹配（regular expression matching）是指输入包含一个长为的字符串与一个长为的字符规律，需要实现一个支持'.'与'*'的正则表达式匹配。为简化实现，'.'与'*'仅可能在中出现。提示，'.'与'*'的匹配规则为：

  • '.'可以匹配任何单个字符
  • 对于任意元素'?'，'?*'可以匹配零个或多个'?'（'*'不会单独出现在的首位，必须搭配前继元素以发挥作用）

如果能够完全匹配整个则返回true，否则返回false。注意，这里的'*'实际上可以对其前一位元素不予考虑，而上一个问题中的'*'至多只能对本处的'*'不予考虑，这是二者的根本差别。例如，当s = 'abc'、p = 'c*abc'时，在本问题中应当返回true，因为'c*abc'可以被视为'abc'；而在上一个问题中则应返回false，因为'c*abc'至多应被视为'cabc'，首位永远为'c'。

正则表达式匹配最好最标准的实现还是通过生成编译原理中的有限状态机，可以参考正则表达式匹配；由动态规划的实现，也有一篇写得很好的文章『 动态规划 』字符串 DP 详解：状态转移推导 + 滚动优化 + 提前结束，可以补充阅读，提供了与本文不一样的视角。

该问题与上一个问题类似，表也应是二维的，定义为的前个元素能否涵盖的前个字符，接下来寻找状态转移方程。

  • 若为文本字符，则

  • 若为'.'，则将右移一位作为

  • 若为'*'，则需要讨论

    • 若为'*'，则视'**'为'*'，

    • 若为'.'，则视'.*'为任意长字符串（但长度不能为零），所以

    • 若为文本字符'x'，则视'x*'为'x'重复任意次的字符串，因此令

      • 当'x*'匹配''，相当于对子字符规律的最后个元素不予考虑，取，则，蕴含有

      • 当'x*'匹配'x'，

      • 当'x*'匹配'xx'，

      • … …

      • 当'*'匹配个'x'，

        其中满足，也就是说当遍历到下一个时，置，重新开始这一匹配流程

      总结下来，当为'*'且为'x'时状态转移可简化为

这个问题用动态规划处理的难点在寻找'x*'时的状态转移。但只要我们逐步分析，问题也能够迎刃而解。

需要注意由于本问题的算法中涉及到的状态转移，所以初始化时不能“简单粗暴”地令第一行与第一列除外均为false，而应当考虑p中的'*'：按行数从小到大遍历，当为'*'时令，否则置false。

根据以上分析，同时注意边界条件，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 输入参数
s = '天馬咲希はいつも明るく、笑顔を絶やさないムードメーカー。'
p = '天馬咲希..**超*絶*笑顔.*'

class Solution:
    # 在每行匹配开始前，初始化dp数组
    def __init_dp_rem(self, dp_1, dp_2, dp_3, p_char, i, n):
        dp_3 = dp_2
        dp_2 = dp_1
        dp_1 = [False for _ in range(n+1)]
        if i == 1:
            dp_2[0] = True
        if p_char == '*':
            dp_1[0] = dp_3[0]
        return dp_1, dp_2, dp_3

    # 正则表达式匹配
    def regexMatching(self, s, p):
        n = len(s)
        m = len(p)
        dp_1 = [False for _ in range(n+1)]  # 在当前匹配中的新数组
        dp_2 = [False for _ in range(n+1)]  # 存储当前匹配中上一次匹配的数组
        dp_3 = [False for _ in range(n+1)]  # 存储当前匹配中上两次匹配的数组

        for i in range(1, m+1):
            if p[i-1] == '*':
                if p[i-2] == '.':
                    dp_1, dp_2, dp_3 = self.__init_dp_rem(dp_1, dp_2, dp_3, p[i-1], i, n)
                    dp_1 = [dp_1[0]] + [True for _ in range(n)]
                elif p[i-2] != '*':
                    dp_1, dp_2, dp_3 = self.__init_dp_rem(dp_1, dp_2, dp_3, p[i-1], i, n)
                    for j in range(1, n+1):
                        dp_1[j] = dp_3[j] or dp_1[j-1] if p[i-2] == s[j-1] else dp_3[j]
            
            elif p[i-1] == '.':
                dp_1, dp_2, dp_3 = self.__init_dp_rem(dp_1, dp_2, dp_3, p[i-1], i, n)
                if not any(dp_2):
                    return False
                dp_1 = [False] + dp_2
                a = dp_1.pop()
            
            else:
                k = 0
                dp_1, dp_2, dp_3 = self.__init_dp_rem(dp_1, dp_2, dp_3, p[i-1], i, n)
                for j in range(1, n+1):
                    dp_1[j] = dp_2[j-1] and (p[i-1] == s[j-1])
                    k += 1
                if k == 0 and p[i] != '*':
                    return False
            
        return dp_1[-1]
            
regex_matching = Solution()
print(regex_matching.regexMatching(s, p))

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

输出：

true

最后，这个算法其实写复杂了些——即便他能正常工作，而且速度与效率也令人满意。原因还是由于涉及到，运用动态数组方法的话，比较直观的想法三个一维数组存储最近匹配的三个行，他们的初始化问题也让人十分头疼（__init_dp_rem__函数）。实际上，完全可以压缩到只使用两个一维数组：将行列转置，即以s对应行、p对应列，然后再以行遍历为大循环、列遍历为小循环。这样不仅代码简洁，连初始化也变得十分容易。

容易分析，造成我们代码繁复的根本原因是：由于状态转移涉及到与，所以在不转置表且以行遍历为大循环的情况下，我们需要同时存储、与，导致我们不得不使用三个一维行向量；同时，对三个一维行向量的初始化也需要在每次行遍历匹配前进行，十分麻烦。转置后的简洁实现可以参考『 动态规划 』字符串 DP 详解：状态转移推导 + 滚动优化 + 提前结束中给出的代码，实现了与我们代码相同的功能，但漂亮了不少。

这告诉我们正确分析了问题后，不能直接一股脑就照着实现代码，得看看怎么写才方便……这个代码写得我太恶心了。

扰乱字符串

前言：这是一个高维动态规划问题。十分推荐先看一看这个可视化视频：ACM 金牌选手教你记忆化搜索。力扣 No.87 扰乱字符串，真·动画教编程，适合语言初学者或编程新人。

这个视频讲明白了扰乱字符串中的递归与动态规划两种实现方式的思路。

# 该问题的表构造是三维的，属于高维动态规划问题。初见时状态不太容易想到。

扰乱字符串（scramble string）是指，我们可以用下述算法扰乱字符串s得到字符串t：

  1. 如果字符串的长度为，算法停止
  2. 如果字符串的长度大于，则执行下述步骤：
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
    • 随机决定是要“交换两个子字符串”还是要“保持这两个子字符串的顺序不变”。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
    • 在 x 和 y 这两个子字符串上继续从步骤1开始递归执行此算法。

现给定两个长度均为的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。该问题的描述引用自87. 扰乱字符串。

按照一贯的做法，似乎我们应该定义状态为的前个字符是否能扰乱为的前个字符。但显然对于这一问题我们并不能这样定义表，否则表除了主对角线上的元素不能确定外，其他位置处均为false（），这样的状态就没有任何意义了，因为扰动字符串的前提是两字符串长度相同，更进一步地要求每个字符在各字符串中的出现次数相同。

现在通过一个具体的例子分析问题，注意到这实际上这是一个二叉树的交换问题，而且s1与s2地位等价（对称）。以字符串'fairy'为例，我们先随机进行二分： 随后我们可以挑选非叶节点'fa'，交换其两个子节点'a'与'f'，得到扰乱字符串'afiry'： 还可以继续交换节点'fa'与'iry'，得到讨乱字符串'iryaf'： 所以'fairy'、'afiry'与'iryaf'就互为扰乱字符串。但'fairy'与'ifyar'却不是，因为不可能经过任何扰乱由'iryaf'得到'ifyar'。

思路：因为一个字符串可能是另一字符串的扰动字符串发前提是两字符串长度相同，故可以用三个指针对s1与s2取相同长度的子串，如令第一个指针与第二个指针分别指向开头与结尾、作用于s1截取子串，令第三个指针则指向s2子串的结尾，再根据s1截取子串的长度确定s2所截取的子串。也可以理解为对两个字符串分别用两个指针截取子串，只不过利用子串长度相同的性质，实际上只需要三个指针。可定义状态表示两个子串是否互为扰乱字符串，其中分别是三个指针所指向的位置，易见为问题的答案。不过，为了方便对状态转移的思考，这里定义状态为以为开头的长为的子串是否与以开为头的长为的子串互为扰乱字符串（注：继续往后讨论才知道为什么这样定义，其中是为了使第三维和第一维、第二维的在程序中同步地从开始计数）。两种的定义方式是完全等价的，没有本质上的区别，这也是子串表示的两种不同的方式，或者说小技巧。在新的定义下，为问题的答案。

要是实在想不到这样定义状态，也可以从最简单、“暴力”的递归与回溯着手考虑，利用备忘录机制进行搜索，也不会花太多时间。对于Python，递归时只需要加上@cache装饰器就好了。若还是一定要用动态规划的方法，可以从这样递归和回溯的思路中寻找灵感——对大多数问题而言，记忆化搜索与动态规划在思想上是等价的、两个算法也是可以相互转换的，除了运行效率上可能有所区别。递归的简洁实现可以参考递归，也是非常好的方法，这里就不实现了，主要讲怎么运用动态规划。

定义了状态后，现在就需要找到状态转移——其实状态转移已经蕴含在问题描述中了，s = x + y正是子问题的分解。我们知道，字符串s1可以被分割为两个子串s1 = x1 + y1，相应地，s2也可以被分割为与s1两个子串相对应的两个子串x2 + y2，那么s1是否为s2的扰乱字符串，就等价于是否存在一组特定的子串x1'、y1'、x2'与y2'，使得x1'为x2'的扰乱字符串且y1'为y2'的扰乱字符串——而后者是前者的子问题的解，于是我们便分解出了子问题，并且最优解依赖于子问题的最优解。但应当注意，由于x、y是可以交换的，所以对于一对确定的x1、y1，实际上存在两对相应的x2、y2，分别记为x21、y21与x22、y22。为方便理解，下作图演示： 除了x21与y21以外，万万不可忽略描述中提到的x + y被允许交换为y + x，因此还必须考虑到x22与y22，否则会漏掉条件： 不过对x1与y1就不必再区分x11、y11与x12、y12了，因为s1与s2地位相同，有轮换对称性，所以考虑一边的交换就可以了，否则会产生重复计算。只要x1与x21互为扰乱字符串且y1与y21互为扰乱字符串时，令x2' = x21、y2'=y21；或者有x1与x22互为扰乱字符串且y1与y22互为扰乱字符串时，令x2' = x22、y2'=y22，这两种情况都可以视为我们找到了s1与s2互为扰乱字符串的证据。

于是算法可以按如下步骤设计：

  1. 当、子串长度为，只需要判断相应字符是否相等，故

  2. 当、子串长度为大于，则根据分析，有 其中，表示长为的x1与x21是否互为扰乱字符串，表示长为的y1与y21是否互为扰乱字符串；表示长为的x1与x22是否互为扰乱字符串，表示长为的y1与y22是否互为扰乱字符串。

可见定义第三维表示长度更方便我们的理解与推导，因为我们是按长度由小到大的顺序逐渐进行状态转移计算的，这就是为什么前文定义第三维代表相对长度的原因。在实际的程序设计中，既可以先遍历，也可以先遍历，这也体现了s1与s2地位相同所带来的对称性——只要最外层循环为的遍历即可。

通过这一状态转移方程可以看出，算法的复杂度为状态数乘状态转移的开销，为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 输入参数
s1 = '重庆大学'
s2 = '学大庆重'

class Solution:
    # 扰乱字符串
    def scrambleString(self, s1, s2):
        n = len(s1)
        dp = [[[False]*n for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i][j][0] = True

        for k in range(1, n):
            for i in range(n-k):
                for j in range(n-k):
                    for m in range(k):
                        if (dp[i][j][m] and dp[i+m+1][j+m+1][k-m-1]) or (dp[i][j+k-m][m] and dp[i+m+1][j][k-m-1]):
                            dp[i][j][k] = True
                            break
        return dp[0][0][n-1]

scramble_tring = Solution()
print(scramble_string.scrambleString(s1, s2))

该算法的空间复杂度为。

输出：

true

同样用Python实现，这个问题用带有备忘录机制的递归写法会比动态规划快上几倍，尽管时间复杂度是相同的。

我怀疑可能是Python的for循环性能太弱导致的，毕竟不得不嵌套了四层for循环。

跳跃游戏Ⅰ

55. 跳跃游戏 - 力扣(LeetCode)：给你一个长为非负整数数组 nums ，你最初位于数组的第一个下标，数组中的每个元素代表你在该位置可以跳跃的最大长度（长度被要求非负）。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

不难想到定义状态为我们能否跳跃至，其中是一个长为的一维布尔数组，并且。在已知的情况下，当集合非空时，意味着是可到达的，此时应赋值为true；否则赋false。

换言之，可以这样定义状态转移方程： 按该状态转移方程写出的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def jumpGame1(self, nums):
        N = len(nums)
        dp = [False for _ in range(N)]
        dp[0] = True
        for n in range(1, N):
            a = []
            for i in range(n):
                if dp[i] == True and i + nums[i] >= n:
                    a.append(i)
            try:
                b = max(a)
                dp[n] = True
            except ValueError:
                dp[n] = False

        return dp[-1]

该算法的时间复杂度为，空间复杂度为。如果在力扣上提交，代码就不出意外地超时，即便最终还是能获得正确的结果。

空间复杂度改进：如果print打印一下数组，会发现数组的内容一定满足如下分布：存在，使得对与，均有与。直观上来理解的话，是由于数组代表的是该位置处我们能够跳跃的最大长度，那么自然地，如果我们能从起点跳跃到、也就是说，也意味着我们同样能够跳跃到位置以前的任何一点、即任何小于的位置所对应的值都应为true；严谨的证明可以考虑数学归纳法，易证。因此，我们记录这样的并更新值即可，而并不必使用一整个布尔数组保存我们的足迹。

时间复杂度改进：沿着空间复杂度改进的思路，我们也没有必要在逐个遍历数组时每一次都进行回溯了，而只需要在每一次的循环中都尽可能地更新到最大的即可，并最终得到问题真正的值。例如，可以令k = max(n+nums[n], k)，则新的状态转移方程为

当n+nums[n]与k相等时提前返回false，当k大于等于N-1时可以提前返回true，否则待循环结束返回true。这里有一些贪心策略的成分，在这样的问题中，我们就很难定义算法是一个贪心算法还是“赤裸”的动态规划；这也从侧面印证，动态规划与贪心算法并不是完全二元对立的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 输入参数
nums = [3,2,1,0,4]

class Solution:
    # 跳跃游戏1
    def jumpGame1(self, nums):
        N = len(nums)
        k = 0
        for n in range(N-1):
            k = max(n+nums[n], k)
            if k == n:
                return False
            elif k >= N-1:
                return True
        return True

jump_game = Solution()
print(jump_game.jumpGame1(nums))

该算法的时间复杂度为，空间复杂度为，改进后算法的性能得到了相当大的提升。

输出：

false

跳跃游戏Ⅱ与优化方案

# 该问题同时也是典型的可以使用单调队列进行算法优化的问题

# 在后文“单调队列与单调栈”中会再次以这个问题为模板讲解新的优化思路

45. 跳跃游戏 II - 力扣(LeetCode)：在跳跃游戏Ⅰ的基础上，求得到达终点（即nums[N-1]）所需的最少跳跃次数。

该问题与跳跃游戏Ⅰ有明显的不同，不可以直接套用跳跃游戏Ⅰ的思路。可以定义为自起点跳跃至所需的最少跳跃次数，那么等于所有至少能到达点的跳跃过程所需的跳跃次数中的最小值再加一，易见，即为所求答案，有状态转移方程： 这里的状态转移方程实际上与前文“最长递增子序列”中的状态转移方程很相似（有发现吗？）！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # 跳跃游戏2
    def jumpGame2(self, nums)
        N = len(nums)
        dp = [0 for _ in range(N)]

        for n in range(1, N):
            dp_k = []
            for k in range(n):
                if k + nums[k] >= n:
                    dp_k.append(dp[k])
            dp[n] = min(dp_k) + 1

        return dp[-1]

该算法的时间复杂度为，空间复杂度为。如果在力扣上提交，几近超时，所以我们需要寻找一些降低时间复杂度的方法。

在力扣上，执行用时花费了11619 ms。

现在我们换一种状态的定义方式，定义为跳跃次的最远距离，这样会更方便我们思考如何降低算法的时间复杂度。当时返回，不难知道，新定义下的状态转移方程为 这样定义的好处是极值问题的目标集合没有了需额外考虑的限制条件，在形式上更简单。然而，如果只是按照该状态转移方程的“字面意思”实现代码，算法的时间复杂度仍然为，不可接受。但我们可以注意到，既然代表跳跃次后的最远距离，那也意味着跳跃次后我们可能出现的位置所构成的集合为（约定：这里虽然用区间表示，但只取范围内的整数）。根据状态转移方程可以知道，在计算时，可能使取得最大值的一定位于，不妨记集合 表示使达到最优的全部可能的，取，则满足：

  3. （前提：一定能通过某种路线跳跃至终点）

第一点与第二点是显而易见的，这里只证明第三点。若但，则根据定义有；同时根据的性质，有，那么，意味着 而该式与矛盾，换言之是与的定义——跳跃次的最远距离矛盾，证毕。

因此，当计算时，我们不必再从中寻找的最小值，因为的第三点性质保证了我们从中的每一个数字集合中都依次任取一个数字，则数字所组成的序列是随所抽取集合的下标而严格单调递增的：这意味着，我们只需要从中寻找的最小值即可。当我们进一步令，此时区间范围最小，搜索范围也随之最小化。 根据改进思路，我们可以大大降低时空开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 输入参数
nums = [1, 2, 3]

class Solution:
    # 跳跃游戏2
    def jumpGame2(self, nums):
        N = len(nums)
        dp = [0]
        k_ast = -1
        dp_max = 0
        n = 0
        
        while dp[n] < N-1:
            n += 1
            for k in range(k_ast+1, dp[n-1]+1):
                dp_k = k + nums[k]
                if dp_k >= dp_max:
                    dp_max = dp_k
                    k_ast = k
            dp.append(dp_max)
        return n
    
jump_game = Solution()
print(jump_game.jumpGame2(nums))

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

输出：

2

在力扣上，执行用时花费了0 ms。即使以1 ms计算，

我们也至少
将速度提升了一万倍

跳跃游戏Ⅲ与跳跃游戏Ⅳ就不可以用动态规划解决了，因为跳跃时允许向前跳跃、也允许向后跳跃，数据结构呈现的关系无法构成一个有向无环图。这类图论搜索问题，可以考虑BFS或DFS。

选择数字

# 该问题同时也是典型的可以使用单调队列进行算法优化的问题

# 在后文“单调队列与单调栈”中会再次以这个问题为模板讲解新的优化思路

选择数字问题：给定个非负整数，现在你可以选择其中若干个数，但不能有超过个连续下标的数字被选择，而你的任务是使得被选出的数字的和最大化。会随数组一同在事先给定。

明显地，这个问题可以用动态规划解决。定义为从数组的前个数中选出的若干数且至多有个数被连续选中的最大和，易见，当时，首先有 如果选中直接插入所对应的最大和序列也不会逾越不可连续挑选超过个数字的规则，那么显然应该让进入最大和序列，因为，这样可以最大化和。现在的第一个问题是，什么时候将计入最大和序列而不会导致有个数被连续选中——即，在计算时，是否每次都考虑了将纳入最大和序列之中。而这就需要回到，从此处开始逐个判断是否有 如果存在任何一个等式不成立，意味着就算直接令插入的最大和序列也不会违背规则，所以此时为了最大化和，应该令。现在的第二个问题是，如果将直接插入原先的最大和序列会违背规则——这时存在个被连续选中的数字，这时的又该如何计算？换句话说，“”应该是什么？显然，我们要么选择不将插入原先的最大和序列、维持原先的最大和序列不变，要么从原先的最大和序列中删除一个符合条件的数字再插入，从而遵守至多有个数字被连续选中的规则。

为达到上述目的，我们可以先用分别替换所对应的最大和序列中的并求和，随后取这些和的最大值，不妨记该值为，然后再将与（即原先的最大和，也可以视为，这样会简化公式的书写）进行比较，取其最大者，接着赋为该值。综上所述，状态转移方程为

现在可以开始编写程序了，尽管按当前分析的细节实现的代码仍然有许多可以优化的地方，但最根本的逻辑大致如此。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 输入参数
nums = [1, 2, 3, 3, 4, 5, 2, 9]
k = 2

class Solution:
    # 选择数字
    def selectNumbers(self, nums, k):
        N = len(nums)
        dp = [0 for _ in range(N+1)]
        
        for n in range(1, N+1):
            ctrl_flag = True  # 用以控制是否进入第二条件下的赋值
            for i in range(1, k):
                if dp[n-i] != dp[n-i-1] + nums[n-i-1]:
                    dp[n] = dp[n-1] + nums[n-1]
                    ctrl_flag = False  # 如果满足第一条件，就不考虑第二条件了
                    break
            
            if ctrl_flag:
                for i in range(n-k, n+1):
                    dp[n] = max(dp[n-1] - nums[i-1] + nums[n-1], dp[n])
                
        return dp[N]

select_numbers = Solution()
print(select_numbers.selectNumbers(nums, k))

该算法的最坏时间复杂度接近，空间复杂度为，还可以进行优化与改进。

输出：

21

糖果的吃法

小冯在接下来的天里想要尽可能多地吃到美味糖果。为了保持健康和节省零花钱，她规定如果今天吃了糖果，明天就不能吃。不过，小冯允许自己有次机会打破这个规则，在连续两天都吃糖果。她希望通过合理安排每天是否吃糖果，获得最大的糖果美味值。你的任务是帮助小冯规划她的吃糖果方案，以使她吃到的糖果美味值最大。例如：小冯在天内有的糖果美味值，她允许自己有次打破原则的机会。最优方案是在第天吃糖果，并在第天使用一次机会继续吃糖果，最大美味值为。

这个问题我起初简单想了一下，状态转移方程竟然没什么头绪。找到了思路后，发现还是最开始的分析不够系统化造成的，导致一旦没了灵感，分析就完全陷入了困境，连头都摸不着。希望通过用系统性的逻辑分析这个问题，提醒我对待问题一定要进行严谨的思考与推理。

显然，我们可以定义状态为前天、使用次破例机会时小冯能享受的最大美味值，那么我们首先要关注的是第天吃不吃糖果，其中选择吃糖果可能会导致非法结果，稍后再做讨论： 现在只需要分析在第天选择吃糖果时的状态转移即可，最后取吃糖果与不吃糖果两个选择下美味值的最大值。

接下来是推导状态转移方程中最重要的一步分析。小冯在第天选择吃糖果时，有两种可能：若第天吃了糖果，那么第天还想吃糖果，就需要使用一次破例机会——如果我们还剩下有破例机会的话；若第天没吃糖果，则美味值应与第的美味值相同（不能思考成了继续讨论第天有没有吃糖果）。不要去想第天到底吃没吃糖果、是不是要做一个条件判断第吃没吃糖果，因为我们最后只需要取一个最大值；也不要去想中间有几天隔一天就吃糖果，那如果在这里使用破例机会怎么办，会不会导致连续好几天的破例……既然验证了该问题具有最优子结构性质，就只需要关注状态的转移！而状态的转移，只需要关注过去的一些状态！这样的思考是设计DFS时的任务，而动态规划利用最优子结构，完全可以避开对“中间过程”的繁琐且不必要的考量。

整理上述逻辑，有：

  • 如果第天小冯选择不吃糖果，则

  • 如果第天小冯试图选择吃糖果，则

    • 如果第天小冯没吃糖果，则小冯能吃到糖果，有

    • 如果第天小冯吃了糖果，则

      • 如果小冯还有破例机会，则小冯能吃到糖果，有

      • 如果小冯没有了破例机会，则小冯吃不到糖果，有

综上所述，记第天小冯吃了糖果时，小冯在第天、已使用次破例机会情况下试图使用破例机会的美味值为，即 则状态转移方程为 最后，返回dp[days]中的最大值即可。注意dp[days][k]不一定是到第天可享用美味值的最大值，应当遍历，取。

现在可以开始编写程序了。不得不说，这是一个很有代表性的需系统分析的动态规划问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 输入参数
k = 1
yummy = [1, 2, 3, 4, 5, 6, 7]

class Solution:
    # 糖果的吃法
    def waysToEnjoyCandies(self, yummy, k):
        days = len(yummy)
        dp = [[0]*(k+1) for _ in range(days+1)]

        for date in range(1, days+1):
            for i in range(k+1):
                try_to_enjoy_Candies = dp[date-1][i-1] + yummy[date-1] if i < k else dp[date-1][i]
                dp[date][i] = max(dp[date-1][i], dp[date-2][i]+yummy[date-1], try_to_enjoy_Candies)
        return max(dp[-1])
    
ways_to_enjoy_candies = Solution()
print(ways_to_enjoy_candies.waysToEnjoyCandies(yummy, k))

该算法的时间复杂度与空间复杂度均为。可以用滚动数组优化空间复杂度至。

输出：

19

状态压缩动态规划

国王游戏与状态压缩

插头动态规划

哈密尔顿回路

国王游戏优化方案

时间复杂度优化

https://space.bilibili.com/8888480/search/video?keyword=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%BC%98%E5%8C%96%E4%B8%93%E9%A2%98

https://www.bilibili.com/video/BV1FF41177Qz/?spm_id_from=333.337.search-card.all.click&vd_source=0f853ad8be7f63b6ea5ac7fe4a6e3c1d

剪枝

决策单调性

上文所给出的算法，在时间开销上显然不能让人满意，这是由于我们在计算时进行了过多而不必要的回溯所导致的。实际上，对于这种动态规划我们有一套方法来优化其时间复杂度。这里主要以跳跃游戏Ⅰ与跳跃游戏Ⅱ为例，说明如何进行这类问题的时间复杂度的优化。

定义：对于类似的状态转移递推式（同理），其中在动态规划前已全部算出、被认为是常量，若时取得最优值，则称为的决策点。由此可知，决策点是关于的函数，记为。如果使得时有，则称该动态规划问题具有决策单调性。

对于满足决策单调性的动态规划，我们可以采取一系列方法以降低其时间复杂度。

经典模型 1：模型一对于，当且仅当时具有决策单调性，该不等式被称为四边形不等式。

改进方法：二分查找 所有状态只能起始状态转移，称均为起始状态的状态序列为序列，不妨设序列的内容均为状态；此时考虑由状态到状态的转移，根据决策单调性，更新后的序列也是单调递增的，形如111...11222...22，故可以通过二分查找寻找从哪一点开始自状态转移到状态更优（决策的末位、决策的始位），将序列从该点及以后的状态均设为状态。对于状态的转移，同理考察；实际的数据可以使用栈来维护，栈中的每一个元素保存一个决策的始末位置。算法的时间复杂度为。

经典模型 2：在模型一的基础上，修改状态转移递推式为，这种情况下若仍满足四边形不等式，则模型也满足决策单调性。

改进方法：分治算法 对于模型二，如果在计算时已知，其中，则可以使用分治算法。顺序枚举，每次利用分治算法计算出所有的，其中，则根据决策单调性，可以将问题分解为两个规模减半的子问题。时间复杂度为。

经典模型 3：对于满足的特殊函数，相应的模型一定满足四边形不等式，从而具备决策单调性。对于这类状态转移递推式，可以将其改写为，从而等价于模型四。

经典模型 4：，其中随单调递增。

改进方法 如果且，则根据的单调性，如果是合法决策，那么也一定可以作为合法决策，因此决策是非法决策，不予考虑。

跳跃游戏Ⅰ实际上可以套用这里的模型进行优化。由于跳跃游戏Ⅰ问题较为简单——没有进行优化的必要性，这里就不做演示了。

单调队列与单调栈

以跳跃游戏Ⅱ为例，说明如何通过单调队列的方法优化时间复杂度。利用单调队列的方法，可以同时应用滚动数组，有可能进一步降低空间复杂度。

高级数据结构

图上的动态规划

Dijkstra算法

地下城游戏

TSP问题

多段图的最短路径

其他领域上的应用

近似串匹配

回溯算法

全排列

背包问题 (回溯)

有别于DP的回溯算法（backtracking algorithm）也可以解决背包问题，而且能够给出最优措施的具体方案，但可能会花费更多的空间与时间。DP的思路是分解问题，回溯的思路是遍历。

01背包问题的回溯算法：

路径

9th，见收藏

八皇后

数独