CONTENT
写在前面
一年一度的蓝桥杯再过几个月就要开始了，博主去年参加了这个比赛拿了省二，多多少少也有一些心得。虽然是很菜的一个奖项，但作为一个数学专业且几乎处处在学数学的蒟蒻，能拿到这个奖已经满意了。
本文实际上来源于我去年备赛的笔记，今天分享出来也是希望能够帮助到准备参加比赛的各位uu们。个人觉得如果你能掌握本文的全部内容并拥有一定的刷题量，拿个奖还是不难的。
废话不多说，直接上干货！
一、输入框架
1. 单个整数输入
n = int(input())
2. 输入一行由空格隔开的整数
a, b = map(int, input().split()) # 用变量存储
arr = list(map(int, input().split())) # 用列表存储
3. 输入大小为 m × n m\times n m×n 的二维整型数组
arr = []
for i in range(m):
arr.append(list(map(int, input().split())))
二、输出框架
1. 输出一行由空格隔开的 n n n 个数
# 方法一
for i in range(n - 1):
print(arr[i], end=' ')
print(arr[n - 1])
# 方法二(推荐)
print(*arr)
2. 输出大小为 m × n m\times n m×n 的二维数组
for i in range(m):
for j in range(n - 1):
print(arr[i][j], end=' ')
print(arr[i][n - 1])
3. print()的用法
print(*objects, sep=' ', end='\n')
# sep是分隔符，默认是空格. end是结尾，默认是换行符.
n = 123
print('|%5d|' % n) # | 123|
print('|%-5d|' % n) # |123 |
print('|%05d|' % n) # |00123|
4. 格式化输出
方法一：
print('%c,%s,%f,%d' % (97, 'abc', 1.0, 2)) # a,abc,1.000000,2
方法二：
print('{} {} {}'.format('a', 'b', 'c')) # a b c
5. 格式化输出浮点数
pi = 3.1415926
print('%.3f' % pi) # 3.142
三、IDLE的用法
ctrl + n 新建 python 文件， F5 运行。
四、常用标准库
4.1 math
1. 数论
math.ceil(3.5) # 4
math.floor(3.5) # 3
math.fabs(-3) # 3.0
math.factorial(4) # 24
math.comb(4, 2) # 6(组合数)
math.isqrt(5) # 2(根号5向下取整)
math.gcd(4, 6) # 2(最大公约数)
math.lcm(4, 6) # 12(最小公倍数)
math.prod([2, 3, 5]) # 30
math.isfinite(x) # x既不是无穷大也不是NaN返回True
math.isinf(x) # x是正或负无穷大，返回True
math.isnan(x) # x是NaN，返回True
2. 数学函数(结果均为浮点数)
math.exp(x)
math.log(x[, base]) # base默认为e
math.pow(x, y) # x的y次方
math.sqrt(x)
math.sin(x)
math.cos(x)
math.tan(x)
3. 常数
math.pi
math.e
math.inf # 浮点正无穷大，对于负无穷大，使用-math.inf，相当于float('inf')
math.nan # 浮点非数字(NaN)值，相当于float('nan')
4.2 random
random.random() # 返回[0.0, 1.0)范围内的一个随机浮点数
random.randint(a, b) # 返回随机整数N满足a<=N<=b
random.choice(seq) # 从非空序列seq中随机选取一个元素
4.3 collections
4.3.1 Counter
Counter 是 dict 的子类，是一个集合，元素像字典键(key)一样存储，它们的计数存储为值。计数可以是任何整数值，包括0和负数。
collections.Counter('aabbccc') # Counter({'c': 3, 'a': 2, 'b': 2})
collections.Counter(['a', 'a', 'b']) # Counter({'a': 2, 'b': 1})
collections.Counter(cats=4, dogs=8) # Counter({'dogs': 8, 'cats': 4})
如果引用的键没有任何记录，并不会报错，而是返回 0：
from collections import Counter
c = Counter(['eggs', 'ham'])
print(c['bacon']) # 0
如果需要删除元素，需使用 del：
del c['eggs']
计数器对象除了字典方法以外，还提供了以下三个方法。
4.3.2 elements()
返回一个迭代器，其中每个元素将重复出现计数值所指定次。 元素会按首次出现的顺序返回。 如果一个元素的计数值小于一，elements() 将会忽略它。
c = Counter(a=4, b=2, c=0, d=-2)
print(list(c.elements())) # ['a', 'a', 'a', 'a', 'b', 'b']
4.3.3 most_common()
返回一个列表，其中包含 n 个最常见的元素及出现次数，按常见程度由高到低排序。 如果 n 被省略或为 None，most_common() 将返回计数器中的 所有 元素。 计数值相等的元素按首次出现的顺序排序：
c = Counter('abracadabra')
print(c.most_common(3)) # [('a', 5), ('b', 2), ('r', 2)]
4.3.4 subtract()
从 迭代对象 或 映射对象 减去元素。输入和输出都可以是0或者负数。
c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
print(c.subtract(d)) # Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})
五、常用小技巧
1. 创建全 0 0 0 的 m × n m\times n m×n 数组
A = [[0] * n for i in range(m)] # 较快
A = [[0 for j in range(n)] for i in range(m)] # 较慢
2. split()
str.split(str="", num=string.count(str)).
- str – 分隔符，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等。
- num – 分割次数。默认为 -1, 即分隔所有。
3. 进制转换
有前缀：
x = 123
print(bin(x)) # 0b1111011(二进制)
print(oct(x)) # 0o173(八进制)
print(hex(x)) # 0x7b(十六进制)
没有前缀：
x = 123
print(format(x, 'b')) # 1111011
print(format(x, 'o')) # 173
print(format(x, 'x')) # 7b
任意进制转换为10进制：
int(x, a)
x 为字符串， 且是 a 进制数。
4. 字符与ASCII码相互转换
print(ord('A')) # 65
print(chr(65)) # A
5. 程序计时
import time
start = time.time()
# 程序
end = time.time()
print(end - start)
6. join()
str.join(seq)
字符串与列表的互相转化：
string = 'abc'
seq = list(string)
print(''.join(seq))
7. lambda函数
语法：
lambda argument_list:expression
argument_list是参数列表，它的结构与Python中函数的参数列表是一样的。expression是一个关于参数的表达式，表达式中出现的参数需要在argument_list中有定义，并且表达式只能是单行的。
下面两个等价：
f = lambda argument_list:expression
def f(argument_list):
return expression
8. filter()
filter(function, iterable) # 返回的是filter类，需要用list转化
例如：
print(list(filter(lambda x: x % 2 == 1, range(1, 10))))
# [1, 3, 5, 7, 9]
9. sorted()
sorted(iterable, key=None, reverse=False)
- iterable – 可迭代对象。
- key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
- reverse – 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
dic = [('a', 3), ('c', 1), ('b', 2)]
print(sorted(dic, key=lambda x: x[0]))
print(sorted(dic, key=lambda x: x[1]))
# [('a', 3), ('b', 2), ('c', 1)]
# [('c', 1), ('b', 2), ('a', 3)]
10. 三元表达式
语法：
为真时的结果 if 判断条件 else 为假时的结果
下面两个等价：
c = max(a, b)
c = a if a >= b else b # if 左边是 a 而不是 c = a
11. exit()
exit()常用于多层循环的退出，它可直接将python程序终止，之后的所有代码都不会继续执行。
12. 遍历列表
假设我们事先不知道数组 nums 的大小，那么有以下两种方法遍历该列表：
# 方法一
n = len(nums)
for i in range(n):
...
# 方法二
for i in range(len(nums)):
...
事实上，方法二比方法一稍微快一点。
六、贪心算法
6.1 基本概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
6.2 硬币问题
问题描述
有1元、5元、10元、50元、100元、500元的硬币各 C 1 , C 5 , C 10 , C 50 , C 100 , C 500 C_1,C_5,C_{10},C_{50},C_{100},C_{500} C1,C5,C10,C50,C100,C500 枚，现在要用这些硬币来支付 A A A 元，最少需要多少枚硬币？
解决方案
贪心算法：优先使用面值大的硬币。
V = [1, 5, 10, 50, 100, 500]
C = list(map(int, input().split())) # 硬币个数列表
A = int(input())
ans = 0
for i in range(5, -1, -1):
t = min(C[i], A // V[i]) # 使用硬币i的枚数
A -= t * V[i]
ans += t
print(ans)
6.3 字典序最小单词
问题描述
给定一个单词，请问在单词中删除 t 个字母后，能得到的字典序最小的单词是什么？
输入格式
输入的第一行包含一个单词，由大写英文字母组成。
第二行包含一个正整数 t。
输出格式
输出一个单词，表示答案
样例输入
LANQIAO
3
样例输出
AIAO
解决方案
贪心算法：从头遍历单词，一旦发现前一个字符的字典序大于后一个字符，则立刻删掉前一个字符，然后再次从头遍历单词。
string = list(input())
t = int(input())
while t:
for i in range(len(string) - 1):
if string[i] > string[i + 1]:
string.pop(i)
t -= 1
break
print(''.join(string))
6.4 翻硬币
问题描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000。
输出格式
一个整数，表示最小操作步数。
解决方案
贪心算法：遍历所有硬币，只要当前硬币与目标状态不同就翻。
init = list(input())
goal = list(input())
# 为了实现翻硬币操作，将正面设为True，反面设为False
for i in range(len(init)):
init[i] = True if init[i] == '*' else False
goal[i] = True if goal[i] == '*' else False
# 遍历所有硬币
ans = 0
for i in range(len(init) - 1):
if init[i] != goal[i]:
init[i], init[i + 1] = not init[i], not init[i + 1]
ans += 1
print(ans)
七、二分搜索
二分搜索只适用于单调上升序列。以下假设数组nums不为空。
7.1 寻找一个数
def binarySearch(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return False
7.2 寻找左侧边界的二分搜索
什么是左侧边界？对于列表 [1,3,3,3,5] 而言，如果我们采用7.1的方法搜索数字
3
3
3，结果返回2。倘若我们需要的是最左侧的那个
3
3
3呢？于是就衍生出了寻找左侧边界的二分搜索算法：
def left_bound(nums, target):
left = 0
right = len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
right = mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left
7.3 寻找右侧边界的二分搜索
def right_bound(nums, target):
left = 0
right = len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left - 1
八、回溯算法
回溯算法的框架如下：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
8.1 全排列
def backtrack(nums, track):
if len(track) == len(nums):
res.append(track[:]) # 浅拷贝
return
for i in range(len(nums)):
if nums[i] in track:
continue
track.append(nums[i])
backtrack(nums, track)
track.pop()
# 全局变量
res = []
track = []
nums = [1, 2, 3]
backtrack(nums, track)
print(res)
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
8.2 N皇后问题
棋盘中皇后可以攻击同一行、同一列，或者左上、左下、右上、右下四个方向的任意单位。现在有一个 N × N N\times N N×N 的棋盘，放置 N N N 个皇后，使得它们不能互相攻击，返回所有可能的结果。
棋盘中的某一格未放置皇后时用 '.' 表示，放置皇后用 'Q' 表示，一个
4
×
4
4\times 4
4×4 的空棋盘的表示方式如下：
['....', '....', '....', '....']
我们首先需要生成棋盘，该函数为
def generateBoard(n):
board = []
for i in range(n):
board.append(''.join(['.' for j in range(n)]))
return board
接下来便是回溯算法的主体框架：
# board中小于row的那些行都已经成功的放置了皇后
# 第row行的所有列都是放置皇后的选择
# 当row=n时，说明棋盘已经放满了(棋盘最后一行的索引是n-1)
def backtrack(board, row):
if row == len(board):
res.append(board[:]) # 浅拷贝
n = len(board)
for col in range(n):
if not isValid(board, row, col):
# 当这样放置皇后不合法时跳过，isValid的具体内容后面会提到
continue
# 将board[row][col]这一格放置皇后
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
backtrack(board, row + 1)
# 撤销选择
board[row] = board[row][:col] + '.' + board[row][col+1:]
最后是isValid函数的具体内容：
def isValid(board, row, col):
"""
判断是否可以在board[row][col]位置处放置皇后
"""
n = len(board)
# 检查列中是否有皇后相互冲突
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查右上方是否有皇后相互冲突
for (i, j) in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i][j] == 'Q':
return False
# 检查左上方是否有皇后相互冲突
for (i, j) in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i][j] == 'Q':
return False
# 之所以不需要考虑左下方和右下方，是因为皇后是逐行从上往下放置的
return True
定义完所有函数之后，我们就可以写出solveNQueens()的主体部分了：
def solveNQueens(self, n: int) -> List[List[str]]:
def generateBoard(n):
# 略
def backtrack(board, row):
# 略
def isValid(board, row, col):
# 略
res = [] # 定义全局变量
board = generateBoard(n)
backtrack(board, 0)
return res
8.3 子集
def backtrack(nums, start, track):
res.append(track[:])
for i in range(start, len(nums)):
track.append(nums[i])
backtrack(nums, i + 1, track)
track.pop()
res = []
track = []
nums = [1, 2, 3]
backtrack(nums, 0, track)
print(res)
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
start 参数实现了“以某个数开头的子集”；而对 res 的更新处在前序遍历的位置，所以 res 记录了树上的所有节点，也就是所有子集。
8.4 组合
输入两个数字 n , k n,k n,k，输出 [ 1 , ⋯ , n ] [1,\cdots,n] [1,⋯,n] 中 k k k 个数字的所有组合。
def backtrack(n, k, start, track):
if len(track) == k:
res.append(track[:])
return
for i in range(start, n + 1):
track.append(i)
backtrack(n, k, i + 1, track)
track.pop()
res = []
track = []
n, k = map(int, input().split())
if n <= 0 or k <= 0:
print(res)
else:
backtrack(n, k, 1, track)
print(res)
例如，当 n = 4 , k = 2 n=4,k=2 n=4,k=2时，算法输出
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
九、广度优先搜索
BFS的核心思想不难理解，就是把一些问题抽象成图，从一个点开始，向四周扩散。一般来说，我们写BFS算法都是用"队列"这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS相对于DFS的最主要区别是：BFS找到的路径一定是最短的，但代价是空间复杂度比DFS大很多。
BFS算法主要用于在一张图中找到从起点start到目标target的最近距离。
BFS框架：
from collections import deque
def bfs(start, target):
"""
start 和 target 都是 Node 类
"""
q = deque([start]) # 核心数据结构——队列
visited = set([start]) # 避免走回头路
step = 0 # 记录扩散的步数
while q:
for i in range(len(q)):
cur = q.popleft()
# 判断是否达到终点
if cur == target:
return step
# 将cur的相邻节点加入队列
for x in cur.adj(): # python没有这种用法，cur.adj()代表cur的相邻节点组成的集合
if x not in visited:
q.append(x)
visited.add(x)
step += 1
return step
9.1 二叉树的最小高度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
q = deque([root])
depth = 1
while q:
for i in range(len(q)):
cur = q.popleft()
if cur.left is None and cur.right is None:
return depth
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
depth += 1
return depth
十、动态规划
10.1 最长递增子序列(Longest Increasing Subsequence)
输入一个无序数组，找到其中最长递增子序列的长度。
例如输入 nums = [10, 9, 2, 5, 3, 7, 101, 18] ，其中最长的递增子序列是 [2, 3, 7, 10] ，所以算法输出的应该是
4
4
4。
用 dp[i] 表示以 nums[i] 这个数为结尾的最长递增子序列的长度。
显然 dp[i] 的初始值为 1 1 1，因为以 nums[i] 为结尾的最长递增子序列至少要包含它自己。
下面寻找状态转移方程。已经知道了 dp[0…i-1]，如何求出dp[i]呢？显然，如果 j < i，且nums[j] < nums[i]，那么nums[i]可以接在nums[j]后面形成一个新的递增子序列，但是我们只选最长的那一个，于是有
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
接下来就可以写出完整的代码了：
nums = list(map(int, input().split()))
n = len(nums)
dp = [1 for i in range(n)]
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
10.2 最长公共子序列(Longest Common Subsequence)
最长公共子序列问题就是让我们求两个字符串的LCS长度。
例如，输入 str1=“abcde”，str2=“aceb”，算法应该输出 3 3 3，因为它们的最长公共子序列是 “ace”，它的长度就是 3 3 3。
对于两个字符串的动态规划问题，一般需要一个二维 dp 数组。对于上述问题，在用动态规划求解时，我们把 str1 视为 " abcde"，即前面多了一个空字符，对 str2 的操作同理。
d p [ i ] [ j ] dp[i][j] dp[i][j] 的含义是，对于 s t r 1 [ 0 , ⋯ , i − 1 ] str1[0,\cdots,i-1] str1[0,⋯,i−1] 和 s t r 2 [ 0 , ⋯ , j − 1 ] str2[0,\cdots,j-1] str2[0,⋯,j−1] ，它们的LCS长度是 d p [ i ] [ j ] dp[i][j] dp[i][j]。对于 d p [ 0 ] [ 3 ] dp[0][3] dp[0][3] ，其含义是空串和"ace"的LCS长度，显然为0。 d p [ 2 ] [ 4 ] dp[2][4] dp[2][4] 的含义是， "ab"和"aceb"的LCS长度。很显然， d p [ 0 ] [ . . . ] dp[0][...] dp[0][...] 与 d p [ . . . ] [ 0 ] dp[...][0] dp[...][0] 都应该初始化为0，这就是base case。
如果
s
t
r
1
[
i
]
=
=
s
t
r
2
[
j
]
str1[i]==str2[j]
str1[i]==str2[j]，说明这个公共字符就在 LCS 中，于是
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
−
1
]
+
1
dp[i][j] = dp[i - 1][j - 1] +1
dp[i][j]=dp[i−1][j−1]+1
如果
s
t
r
1
[
i
]
!
=
s
t
r
2
[
j
]
str1[i] != str2[j]
str1[i]!=str2[j]，说明
s
t
r
1
[
i
]
str1[i]
str1[i]和
s
t
r
2
[
j
]
str2[j]
str2[j]这两个字符至少有一个不在LCS中，那到底哪个字符不在LCS中呢？我们都试一下：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
)
dp[i][j] = \max(dp[i - 1][j],dp[i][j-1])
dp[i][j]=max(dp[i−1][j],dp[i][j−1])
def longestCommonSubsequence(str1, str2):
m = len(str1)
n = len(str2)
dp = [[0] * (n + 1) for i in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[m][n]
10.3 最长回文子序列
输入一个字符串 s，找出 s 中的最长回文子序列长度。
比如输入 s = “aecda”，算法返回 3，因为最长回文子序列是 “aca”，长度为 3。
这个问题对 dp 数组的定义是：在子串 s [ i ⋯ j ] s[i\cdots j] s[i⋯j] 中，最长回文子序列的长度为 d p [ i ] [ j ] dp[i][j] dp[i][j]。
如果相求 d p [ i ] [ j ] dp[i][j] dp[i][j]，假设知道了子问题 d p [ i + 1 ] [ j − 1 ] dp[i+1][j-1] dp[i+1][j−1]的结果（即 s [ i + 1 , ⋯ , j − 1 ] s[i+1,\cdots ,j-1] s[i+1,⋯,j−1]中最长回文子序列的长度），能否想办法算出 d p [ i ] [ j ] dp[i][j] dp[i][j] 的值呢？
当然可以，这取决于 s [ i ] s[i] s[i] 和 s [ j ] s[j] s[j] 的字符。
如果它俩相等，那么它俩加上 s [ i + 1 , ⋯ , j − 1 ] s[i+1,\cdots,j-1] s[i+1,⋯,j−1]中的最长回文子序列就是 s [ i ⋯ j ] s[i\cdots j] s[i⋯j]的最长回文子序列。
如果它俩不等，说明它俩不可能同时出现在 s [ i ⋯ j ] s[i\cdots j] s[i⋯j]的最长回文子序列中，那么把它俩分别加入 s [ i + 1 , ⋯ , j − 1 ] s[i+1,\cdots,j-1] s[i+1,⋯,j−1]中，看看哪个子串产生的回文子序列更长即可。
以上两种情况写成代码就是这样：
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
下面明确 base case，如果只有一个字符，显然最长回文子序列长度是1，也就是 d p [ i ] [ j ] = 1 ( i = = j ) dp[i][j] = 1(i==j) dp[i][j]=1(i==j)。
因为 i 肯定小于等于 j，所以对于那些 i > j 的位置，根本不存在什么子序列，应该初始化为0。
根据之前的状态转移方程，想求 d p [ i ] [ j ] dp[i][j] dp[i][j] 需要知道 d p [ i + 1 ] [ j − 1 ] dp[i+1][j-1] dp[i+1][j−1]， d p [ i + 1 ] [ j ] dp[i+1][j] dp[i+1][j]， d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]这三个位置，它们位于 d p [ i ] [ j ] dp[i][j] dp[i][j]的左下方，为了保证每次计算 d p [ i ] [ j ] dp[i][j] dp[i][j]，左下方的位置已经被计算出来，只能斜着遍历或反着遍历。
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for i in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
写在最后
- 创作不易，如果这篇文章有帮助到你，还想请你点个赞支持一下博主~
- 可能会有部分地方有笔误，如有发现可以在评论区留言
- 文章版权归博主所有，如需转载请注明出处