CONTENT

• 写在前面
• 一、输入框架
• 二、输出框架
• 三、IDLE的用法
• 四、常用标准库
• • 4.1 math
  • 4.2 random
  • 4.3 collections
  • • 4.3.1 Counter
    • 4.3.2 elements()
    • 4.3.3 most_common()
    • 4.3.4 subtract()
• 五、常用小技巧
• 六、贪心算法
• • 6.1 基本概念
  • 6.2 硬币问题
  • 6.3 字典序最小单词
  • 6.4 翻硬币
• 七、二分搜索
• • 7.1 寻找一个数
  • 7.2 寻找左侧边界的二分搜索
  • 7.3 寻找右侧边界的二分搜索
• 八、回溯算法
• • 8.1 全排列
  • 8.2 N皇后问题
  • 8.3 子集
  • 8.4 组合
• 九、广度优先搜索
• • 9.1 二叉树的最小高度
• 十、动态规划
• • 10.1 最长递增子序列(Longest Increasing Subsequence)
  • 10.2 最长公共子序列(Longest Common Subsequence)
  • 10.3 最长回文子序列
• 写在最后

写在前面

一年一度的蓝桥杯再过几个月就要开始了，博主去年参加了这个比赛拿了省二，多多少少也有一些心得。虽然是很菜的一个奖项，但作为一个数学专业且几乎处处在学数学的蒟蒻，能拿到这个奖已经满意了。

本文实际上来源于我去年备赛的笔记，今天分享出来也是希望能够帮助到准备参加比赛的各位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]

写在最后

• 创作不易，如果这篇文章有帮助到你，还想请你点个赞支持一下博主~
• 可能会有部分地方有笔误，如有发现可以在评论区留言
• 文章版权归博主所有，如需转载请注明出处