关键字：dp
简简单单，二维dp，直接第一版👇
m, n = map(int, input().split())
k = int(input())
ll = [tuple(map(int, input().split())) for _ in range(k)]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1 if (i - 1, j - 1) in ll else max(dp[i - 1][j], dp[i][j - 1])
print(dp[m][n])
好，超时+超内存
欸那就把保存点集的list改成set吧，时间上查找效率能提高很多
每一次对行遍历的时候好像只需要下面一行，那就可以只开一维dp，在遍历的时候直接覆盖上一层内容，内存直接缩小10^6倍~
第二版👇
m, n = map(int, input().split())
k = int(input())
ll = {tuple(map(int, input().split())) for _ in range(k)}
dp = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[j] = max(dp[j], dp[j - 1]) + 1 if (i - 1, j - 1) in ll else max(dp[j], dp[j - 1])
print(dp[n])
欸36分变63分，还是超时，内存倒是不超了，但是连测试点7都跑了两秒多（就当它数据量是递增的），想不出怎么优化了。。
搜！
学到个新词：离散化
大致就是把所有点压缩来缩小dp数组的范围，避免了很多空的dp数组，原dp范围是10^6^2，确实要超时，因为本题中x轴和y轴是递增dp的，所以可以离散化，把所有点xy轴保存起来，然后排个序，从小到大，按索引作为键、坐标作为值建一个字典来查找，这时dp范围就只剩下一维的len(sort)^2了
最终版👇
m, n = map(int, input().split())
k = int(input())
sort = set()
points = set()
for _ in range(k):
a, b = map(int, input().split())
points.add((a, b))
sort.add(a)
sort.add(b)
sort = sorted(sort)
find = {i: j for i, j in enumerate(sort)}
dp = [0] * (len(sort) + 1)
for i in range(1, len(sort) + 1):
for j in range(1, len(sort) + 1):
dp[j] = max(dp[j], dp[j - 1]) + 1 if (find[i - 1], find[j - 1]) in points else max(dp[j], dp[j - 1])
print(dp[-1])
