目录
最长公共子序列（Longest Common Subsequence）
最长上升子序列（Longest Increasing Subsequence）
图的颜色问题（Graph Coloring Problem）
python常用算法总结
最大子数组和（Kadane’s Algorithm）
Kadane’s算法用于查找具有最大和的连续子数组。
def kadane(arr):
max_so_far = arr[0]
max_ending_here = arr[0]
for i in range(1, len(arr)):
max_ending_here = max(arr[i], max_ending_here + arr[i])
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# ⽰例
print(kadane([1, -3, 2, 1, -1]))最长公共子序列（Longest Common Subsequence）
LCS用于查找两个字符串的最长公共子序列。
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
# ⽰例
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))编辑距离（Edit Distance）
编辑距离用于计算两个字符串之间转换的最少操作数。
def edit_distance(str1, str2):
m = len(str1)
n = len(str2)
dp = [[0 for x in range(n+1)] for x in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
return dp[m][n]
# ⽰例
str1 = "sunday"
str2 = "saturday"
print(edit_distance(str1, str2))背包问题（Knapsack Problem）
背包问题用于在不超过背包容量的情况下选择物品以获得最大价值。
def knapSack(W, wt, val, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
# ⽰例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))最长上升子序列（Longest Increasing Subsequence）
LIS用于查找最长的严格上升子序列。
def lis(arr):
n = len(arr)
lis = [1]*n
for i in range(1, n):
for j in range(0, i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j]+1
maximum = 0
for i in range(n):
maximum = max(maximum, lis[i])
return maximum
# ⽰例
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))汉诺塔问题（Tower of Hanoi）
汉诺塔问题是经典的递归问题，涉及移动圆盘。
def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 1:
print("Move disk 1 from rod", from_rod, "to rod", to_rod)
return
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)
# ⽰例
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')N皇后问题（N-Queens Problem）
N皇后问题涉及在N x N的棋盘上放置N个皇后，使得它们彼此之间不会攻击。
def print_solution(board):
for i in board:
print(" ".join(str(x) for x in i))
def is_safe(board, row, col, n):
for i in range(col):
if board[row][i] == 1:
return False9
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, n, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_nq_util(board, col, n):
if col >= n:
return True
for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
if solve_nq_util(board, col + 1, n):
return True
board[i][col] = 0
return False
def solve_nq(n):
board = [[0 for j in range(n)] for i in range(n)]
if not solve_nq_util(board, 0, n):
print("Solution does not exist")
return False
print_solution(board)
return True
# ⽰例
n = 4
solve_nq(n)
Rat in a Maze
Rat in a Maze问题是经典的回溯问题，涉及找到迷宫的所有可能路径。
def is_safe(maze, x, y, n):
if x >= 0 and x < n and y >= 0 and y < n and maze[x][y] == 1:
return True
return False
def solve_maze_util(maze, x, y, sol, n):
if x == n - 1 and y == n - 1 and maze[x][y] == 1:
sol[x][y] = 1
return True
if is_safe(maze, x, y, n):
if sol[x][y] == 1:
return False
sol[x][y] = 1
if solve_maze_util(maze, x + 1, y, sol, n):
return True
if solve_maze_util(maze, x, y + 1, sol, n):
return True
if solve_maze_util(maze, x - 1, y, sol, n):
return True
if solve_maze_util(maze, x, y - 1, sol, n):
return True
sol[x][y] = 0
return False
def solve_maze(maze):
n = len(maze)
sol = [[0 for j in range(n)] for i in range(n)]
if not solve_maze_util(maze, 0, 0, sol, n):
print("Solution does not exist")
return False
print_solution(sol)
return True
# ⽰例
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
solve_maze(maze)50图的颜色问题（Graph Coloring Problem）
图的颜色问题涉及为图的顶点着色，使得相邻顶点不具有相同颜色。
def is_safe(v, graph, color, c):
for i in range(len(graph)):
if graph[v][i] == 1 and color[i] == c:
return False
return True
def graph_coloring_util(graph, m, color, v):
if v == len(graph):
return True
for c in range(1, m + 1):
if is_safe(v, graph, color, c):
color[v] = c
if graph_coloring_util(graph, m, color, v + 1):
return True
color[v] = 0
def graph_coloring(graph, m):
color = [0] * len(graph)
if not graph_coloring_util(graph, m, color, 0):
print("Solution does not exist")
return False
print("Solution exists: ", color)
return True
# ⽰例
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
m = 3
graph_coloring(graph, m)约瑟夫斯问题（Josephus Problem）
约瑟夫斯问题涉及找到最后一个幸存者的位置。
def josephus(n, k):
if n == 1:
return 0
else:
return (josephus(n - 1, k) + k) % n
# ⽰例
n = 7
k = 3
print("The chosen place is ", josephus(n, k))集合划分问题（Partition Problem）
集合划分问题涉及将给定的集合划分为两个子集，使得它们的和相等。
def is_subset_sum(arr, n, sum):
subset = [[False for i in range(sum + 1)] for i in range(n + 1)]
for i in range(n + 1):
subset[i][0] = True
for i in range(1, sum + 1):
subset[0][i] = False
for i in range(1, n + 1):
for j in range(1, sum + 1):
if j < arr[i - 1]:
subset[i][j] = subset[i - 1][j]
if j >= arr[i - 1]:
subset[i][j] = (subset[i - 1][j] or subset[i - 1][j - arr[i - 1]])
return subset[n][sum]
def find_partition(arr, n):
sum = 0
for i in range(n):
sum += arr[i]
if sum % 2 != 0:
return False
return is_subset_sum(arr, n, sum // 2)
# ⽰例
arr = [3, 1, 5, 9, 12]
n = len(arr)
if find_partition(arr, n) == True:
print("Can be divided into two subsets of equal sum")
else:
print("Cannot be divided into two subsets of equal sum")字符串匹配（KMP算法）
KMP算法用于在文本中查找给定的模式字符串。
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
lps = [0]*M
j = 0
computeLPSArray(pat, M, lps)
i = 0
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print("Found pattern at index " + str(i-j))
j = lps[j-1]
elif i < N and pat[j] != txt[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):27 length = 0
lps[0] = 0
i = 1
while i < M:
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length-1]
else:
lps[i] = 0
i += 1
# ⽰例
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)