这边来盘点一下常见的编程题思路。这节主要盘点一下动态规划的几个常见思路。

动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划能够降低复杂度的关键是存在子问题重叠，加速来自于避免重复求解相同的子问题。因此，如果确定要使用动态规划，必须要合理定义子问题。这并不简单，因此在这里盘点一下常见的思路。

动态规划五步法

看到B站有个up主说的五步法挺好的，在这里总结一下：

第一步：确定状态转移方程 状态转移方程是描述子问题之间关系的数学表达式。它表示当前状态如何通过一系列决策转移到下一个状态。对于每个子问题，我们需要确定其状态转移方程，以便使用它来求解子问题。

第二步：根据状态转移方程求解子问题 在确定了状态转移方程之后，我们需要求解每个子问题以找到最优解。这一步通常涉及到迭代计算，即反复使用状态转移方程来计算每个子问题的最优解。

第三步：初始化动态规划表 动态规划表是一个二维数组，用于存储每个子问题的最优解。在初始化阶段，我们需要将动态规划表的所有元素初始化为0或无解。这一步是必要的，因为动态规划算法依赖于表中存储的信息来找到最优解。

第四步：确定状态转移顺序 在确定了状态转移方程和初始化了动态规划表之后，我们需要确定状态转移的顺序。对于一维动态规划问题，通常采用自底向上的方法进行状态转移，而对于二维动态规划问题，则采用自上向下的方法进行状态转移。选择正确的状态转移顺序可以提高算法的效率。

第五步：处理边界条件 在求解动态规划问题时，我们需要注意边界条件。边界条件是指问题的限制条件或初始条件，它们确定了问题的可行解范围。在处理边界条件时，我们需要将其纳入状态转移方程和初始化的过程中，以确保最终找到的解是符合条件的。

最长上升子序列

牛客链接：https://www.nowcoder.com/share/jump/6002236101726202184500

子问题定义：dp[i]以第i个元素结尾的最长上升子序列。填表完之后整个序列的最大值就算最长上升子序列。

子问题解决：

列出递推关系式： \[ dp[i] = \left \{ \begin{aligned} 1,& i=1, \\ \max (1, dp[j]+1), & i>1, j<i, arr[j]<arr[i] \end{aligned} \right . \] 编程解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        dp = [1 for i in range(len(arr))]

        for i in range(len(arr)):
            tmp_max_length = 1  # 最少是1
            for j in range(i):
                # 往前看看有没有比该元素更小的元素
                # 有的话加入该元素可以组成一个新的更长的严格上升子序列
                if arr[j] < arr[i] and dp[j] + 1 > tmp_max_length:
                        tmp_max_length = dp[j] + 1
            dp[i] = tmp_max_length
        
        return max(dp) if len(dp) > 0 else 0

思路解析：

一般子序列的问题都可以考虑建模为以第i个字符/数字结尾的子序列，然后一般在这个子序列后面加数字/字符就不需要重复求解前面的子问题了。

最长公共子序列

牛客链接：https://www.nowcoder.com/share/jump/6002236101726203662281

子问题定义：dp[i][j]表示以s1的前i个字符串，以s2的前j个字符串的最长公共子序列长度。填表完之后整个二维数组的最后一个元素\(dp[-1][-1]\)即为最长公共子序列的长度。

子问题解决：

初始值：dp[i][0]=0, dp[0][j]=0

递推式： \[ dp[i][j] = \left \{ \begin{aligned} dp[i-1][j-1] + 1,& \text{if}\ s[i-1]==s[j-1] \\ \max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]), & \text{otherwise} \\ \end{aligned} \right . \] 这里面严格有\(dp[i-1][j-1] \leq dp[i-1][j]\)和\(dp[i-1][j-1] \leq dp[i][j-1]\)，因此实际最后一项可以消除。

编程解决：

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
class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        n = len(s1)
        m = len(s2)
        dp = [[0]*(m+1) for i in range(n+1)]

        for i in range(1, n+1):
            for j in range(1, m+1):
                # 判断字符是否在最长子序列中
                if s1[i-1] == s2[j-1]:
                    # 该字符一定在最长子序列中
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # 如果不等的话有3种情况，
                    # s1[i]是、s2[j]是或者两者都不是
                    # 第三种情况可以被前两种组合表示
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        
        # 通过回溯构造解
        i, j = n, m
        k = dp[i][j]
        lcs = ""
        while i > 0 and j > 0 and k > 0:
            while dp[i][j] == dp[i-1][j] and i > 0:
                i = i - 1
            while dp[i][j] == dp[i][j-1] and j > 0:
                j = j - 1

            lcs = s1[i-1] + lcs
            i -= 1
            j -= 1
            k -= 1

        return lcs if lcs else "-1"

思路解析：

这个公共子序列问题需要用到前i个字符构造子序列，核心还是对于n个字符的字符串s1和m个字符的字符串s2，如果有s1[n-1]==s2[m-1]，那么最长公共子序列一定是字符串s1前n-1个字符和字符串s2前m-1个字符最长公共子序列+1。如果不等，是s1去掉最后一个字符或者s2去掉最后一个字符组成新字符串的最长公共子序列的值。怎么构造子问题取决于问题本身的性质。

最长公共子串

牛客链接：https://www.nowcoder.com/share/jump/6002236101726215200550

子问题定义：子串和子序列不一样，子串必须是连续的字符，因此以第i个字符结尾的最长子串严格依赖于第i-1个字符，这和最长上升子序列有一点类似。可以定义dp[i][j]为以s1中第i个字符结尾，s2中以第j个字符结尾的最长公共子串的值。填表完之后整个数组的最大值就算最长公共子串的值。

子问题解决：

初始值：dp[0][j]=0, dp[i][0]=0

递推式： \[ dp[i][j] = \left \{ \begin{aligned} dp[i-1][j-1] + 1,& \text{if}\ s1[i]==s2[j] \\ 0,& \text{otherwise} \end{aligned} \right . \] 编程解决：

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
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        n, m = len(str1), len(str2)

        if n == 0 or m == 0:
            return ""

        # 动态规划
        dp = [[0 for j in range(m+1)] for i in range(n+1)]

        # 记录最大值
        max_value = 0
        max_i, max_j = -1, -1

        for i in range(1, n+1):
            for j in range(1, m+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0

                if dp[i][j] > max_value:
                    max_value = dp[i][j]
                    max_i, max_j = i, j

        # 返回最长字符串
        if max_value == 0:
            return ""
        else:
            return str1[max_i-max_value: max_i]

思路解析：

最长公共子串算是比较简明的动态规划问题，但需要和最长公共子序列区别开来。

回溯法

这是模拟题必须要会的一个方法，本质上是在解空间执行深度优先搜索。我们整理一套模板以供快速编写代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def dfs(v):
    advance(v)  # 进入，一般不会做别的事
    if isLeaf(v):
        remark(v)  # 视情况对叶子节点，也即解做操作
    else:
        # 获取当前状态的所有解空间
        e = nextAdj(v, None)
        while e is not None:
            if not exceedBound(v + [e]):
                v.append(e)
                dfs(v)
            e = nextAdj(v, e)
    # 回溯
    if len(v)>0:
        del v[-1]

dfs([])

图

本来不想写这章的，但架不住要考，我真服了。还是回顾一些经典的图算法好了。

最小生成树问题

这里要用到对解决最小生成树问题一个非常重要的数据结构，即并查集(Disjoint-set data structure, DSU)。我们先介绍这个数据结构：

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

实际实现是通过列表去管理每个node对应的根节点的，代码还是比较容易理解的：

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
class DSU:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.rank = [1 for i in range(N)]
    
    def find(self, k):
        if self.root[k] == k:
            return k
        return self.find(self.root[k])
    
    def union(self, node1, node2):
        # 查找根
        x = self.find(node1)
        y = self.find(node2)
        if x == y:
            return False
        
        # 比较秩
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        
        # 执行合并操作
        self.rank[x] += self.rank[y]
        self.root[y] = x
        return True

其中self.root里面存放每个node对应的根节点，开始时初始化为其本身，一旦开始合并就将根节点指向另一个node。而self.rank则是防止整个并查集查找时退化为链表形式，它进行合并操作时始终保持将管理元素多的node作为根节点，从而减少多次触发查找的概率。

有了这个数据结构，也就为后续扫清了障碍，我们继续介绍解决最小生成树的两种算法——Prim算法和Kruskal算法。

Prim算法的时间复杂度为O(N^2), N为顶点数量, 适合于稠密图或者完全图

Kruskal算法时间复杂度为O(M*log(M)), M为边数, 适合于稀疏图

Prim算法

Prim算法是以点为核心的最小生成树算法。它的思想是维护两个集合selected_nodes和candidate_nodes，selected_nodes初始化是加入任意一个节点，而candidate_nodes则初始化为除加入到selected_nodes集合中的所有节点。之后遍历以selected_nodes中节点为开始节点，以candidate_nodes节点为结束节点的边，选择其中最小的边加入。

python示意代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
selected_nodes = {0}
candidate_nodes = {i for i in range(1, N)}

# 逐步加入
selected_edge_num = 0
while selected_num < N-1:
    step_min_cost = float('inf')
    start, end = 0, 0
    for i in selected_nodes:
        for j in candidate_nodes:
            if distance_map[i][j] < min_cost:
                step_min_cost = distance_map[start][end]
                start = i
                end = j
    # 更新选择节点
    selected_nodes.add(end)
    candidate_nodes.remove(end)
    selected_edge_num += 1
    min_cost += step_min_cost

当然，这是上面思想的直接翻译版本，实际中这样重复求解了很多次candidate_node到selected_node的最小距离。因为每次新增一个节点，对于一些节点到整个生成树最小距离只会受这个更新节点影响，不需要重复求解旧节点了，可以复用之前的结果。因此，我们可以维护一个d数组来保存节点到生成树的最小距离，之后添加节点时更新该数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
d = [float('inf') for i in range(N)]
vis = [False for i in range(N)]
d[0] = 0
for _ in range(N):
    # 寻找这轮最小d
    step_min_cost = float('inf')
    node = 0
    for i in range(N):
        if not vis[i] and d[i] < step_min_cost:
            node = i
            step_min_cost = d[i]
    vis[node] = True
    min_cost += step_min_cost

    # 更新与这个顶点相连的最小距离
    for i in range(N):
        if not vis[i]:
            d[i] = min(distance_map[i][node], d[i])

kruskal算法

kruskal则是以边为核心的最小生成树算法，对边的权值进行排序，然后从小到大决定边是否加入最小生成树中。是否加入最小生成树取决于该边的开始节点和结束节点是否连通，如果不连通则需要加入，反之不需要。这里可以利用并查集来确定开始节点和结束节点是否连通。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
edges.sort(key=lambda x: x[2])

# 执行kruskal算法
dsu = DSU(N)
min_cost = 0
selected_edge_num = 0
for start, end, weight in edges:
    if dsu.union(start, end):
        min_cost += weight
        selected_edge_num += 1

        if selected_edge_num == N-1:
            break

经典例题

以leetcode上的一道经典问题作为结束。lc链接：https://leetcode.cn/problems/min-cost-to-connect-all-points

Prim算法解法：

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
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 1:
            return 0

        N = len(points)
        # prim算法
        selected_nodes = {0}
        candidate_nodes = set([i for i in range(1, N)])
        min_cost = 0

        # 计算两两之间距离
        distance_map = [[0 for i in range(N)] for j in range(N)]
        for i in range(N):
            for j in range(i+1, N):
                distance_map[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                distance_map[j][i] = distance_map[i][j]

        d = [float('inf') for i in range(N)]
        vis = [False for i in range(N)]
        d[0] = 0
        for _ in range(N):
            # 寻找这轮最小d
            step_min_cost = float('inf')
            node = 0
            for i in range(N):
                if not vis[i] and d[i] < step_min_cost:
                    node = i
                    step_min_cost = d[i]
            vis[node] = True
            min_cost += step_min_cost

            # 更新与这个顶点相连的最小距离
            for i in range(N):
                if not vis[i]:
                    d[i] = min(distance_map[i][node], d[i])
        
        return min_cost

kruskal算法解法：

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
class DSU:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.rank = [1 for i in range(N)]
    
    def find(self, k):
        if self.root[k] == k:
            return k
        return self.find(self.root[k])
    
    def union(self, node1, node2):
        # 查找根
        x = self.find(node1)
        y = self.find(node2)
        if x == y:
            return False
        
        # 比较秩
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        
        # 执行合并操作
        self.rank[x] += self.rank[y]
        self.root[y] = x
        return True

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 1:
            return 0

        N = len(points)
        # kruskal算法
        selected_nodes = [0]
        candidate_nodes = [i for i in range(N)]

        # 计算两两之间距离
        distance_map = [[0 for i in range(N)] for j in range(N)]
        for i in range(N):
            for j in range(i+1, N):
                distance_map[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                distance_map[j][i] = distance_map[i][j]
        
        edges = []
        for i in range(N):
            for j in range(i+1, N):
                edges.append((i, j , distance_map[i][j]))
        edges.sort(key=lambda x: x[2])

        # 执行kruskal算法
        dsu = DSU(N)
        min_cost = 0
        selected_edge_num = 0
        for start, end, weight in edges:
            if dsu.union(start, end):
                min_cost += weight
                selected_edge_num += 1

                if selected_edge_num == N-1:
                    break
        
        return min_cost

数学

有一部分题目和数学知识紧密相关，也希望能够掌握跟数学有关的常见问题解法。

最小公倍数

最小公倍数(LCM)是让人比较难想到的问题之一，因为如果直接从乘积空间枚举往往产生很高的计算复杂度。对于这个问题的正解是借助以下公式进行分解： \[ lcm(x,y) = \frac{x*y}{gcd(x,y)} \] 其中，\(lcm\)表示求两数最小公倍数，\(gcd\)表示求两数的最大公约数。求最大公约数可以用欧几里得算法在对数时间复杂度内解决： \[ gcd(x,y) = \left \{ \begin{aligned} x,&\ \text{if}\ y=0 \\ gcd(y,x\%y),&\ \text{otherwise} \end{aligned} \right . \] 这样，我们可以编写出在对数时间复杂度下求最小公倍数的算法：

1
2
3
4
5
6
def gcd(x, y):
    if y:
        x, y = y, x%y

def lcm(x, y):
    return (x * y) // gcd(x, y)