蓝桥-线性DP

最长公共子序列

dp[i][j]，A序列前i个和B序列的前j个的最长公共子序列。

最长递增序列（蓝桥骑士）

题目：

https://www.lanqiao.cn/problems/1188/learning/

DP代码（超时）

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = 1
"""
dp[i]，前i个数中最长的递增系列长度
将a[i]放到i-i个数后面的时候，
找到前面i-1个数当中，找到值比a[i]小的那些位置的dp中最大加1
"""
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
# print(dp)
print(dp[-1])

二分代码

import bisect
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    # 找到a[i]应该在b里的哪个位置
    pos = bisect.bisect_left(b, a[i])
    # print(a[i],pos)
    if pos == len(b):  # 接在b的最后
        b.append(a[i])
    else:  # 插入a[i]
        b[pos] = a[i]
    # print(b)
print(len(b))

编辑距离（字符串转换）

题目

https://www.lanqiao.cn/problems/1507/learning/

代码

s = "." + input()
t = "." + input()
n, m = len(s), len(t)
dp = [[0] * m for _ in range(n)]
for i in range(n):
    dp[i][0] = i
for i in range(m):
    dp[0][i] = i
for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            # 相同，操作数=去掉这俩字符的操作数
            dp[i][j] = dp[i - 1][j - 1]
        else:
            # 不相同，可以有三种情况
            # 1 删掉s[i] + s前i-1个t前j个
            # 2 s后面添加t[j] + s前i个t前j-1个
            # 3 s[i]替换成t[j] + s前i-1个t前j-1个
            dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
print(dp[n - 1][m - 1])

网格图上的DP

题目：过河卒

https://www.lanqiao.cn/problems/755/learning/

代码

b1, b2, h1, h2 = map(int, input().split())
dp = [[0] * (b2 + 1) for _ in range(b1 + 1)]
h = []
for di, dj in [(-1, -2), (-2, -1), (-2, 1), (-1, 2),
               (1, 2), (2, 1), (2, -1), (1, -2), (0, 0)]:
    ni, nj = h1 + di, h2 + dj
    if 0 <= ni <= b1 and 0 <= nj <= b2:
        h.append((ni, nj))
for i in range(b1 + 1):
    if (i, 0) not in h:
        dp[i][0] = 1
    else:
        break
for i in range(b2 + 1):
    if (0 ,i) not in h:
        dp[0][i] = 1
    else:
        break
for i in range(1, b1 + 1):
    for j in range(1, b2 + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] if (i, j) not in h else 0
print(dp[b1][b2])

积木画

https://www.lanqiao.cn/problems/2110/learning/

mod = 1000000007
n = int(input())
a = [[2], [1], [1]]
mat = [[1, 2, 1],
       [0, 1, 1],
       [1, 0, 0]]


def mat_mult(A, B):
    # A:ra*ca B:ca*cb C:ra*cb
    ra, ca, cb = len(A), len(A[0]), len(B[0])
    res = [[0] * cb for _ in range(ra)]
    for i in range(ra):
        for j in range(cb):
            for k in range(ca):
                res[i][j] += (A[i][k] * B[k][j]) % mod
    return res


def mat_quick_mult(n, ma):
    tmp = [[1, 0, 0],
           [0, 1, 0],
           [0, 0, 1]]
    while n:
        if n & 1:
            tmp = mat_mult(ma, tmp)
        ma = mat_mult(ma, ma)
        n >>= 1
    return tmp


if n == 2:
    print(2)
elif n == 3:
    print(5)
elif n == 1:
    print(1)
else:
    t = mat_quick_mult(n - 2, mat)
    res = mat_mult(t, a)
    print(res[0][0]%mod)

采药

https://www.lanqiao.cn/problems/563/learning/

T, M = map(int, input().split())
t = [0]
v = [0]
for _ in range(M):
    tt, vv = map(int, input().split())
    t.append(tt)
    v.append(vv)
dp = [0] * (T + 1)  # for _ in range(M + 1)]
for i in range(1, M + 1):
    for j in range(T, t[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - t[i]] + v[i])
print(dp[-1])

摆花

https://www.lanqiao.cn/problems/389/learning/

import sys

FileInput = False

if FileInput:
    sys.stdin = open('flower.in', 'r')
    sys.stdout = open('flower.out', 'w')
mod = 10 ** 6 + 7
# n种花，一共m盆
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
# dp[i][j]，编号1~i的花放j个盆有多少方案数
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, a[1] + 1):
    dp[1][i] = 1
for i in range(1, n + 1):
    dp[i][0] = 1
    # dp[i][1] = i # a[i[可能是0
for i in range(2, n + 1):
    for j in range(1, m + 1):
        # 不是所有花都要放
        # 第i号花放k个位置，k的范围是[0,a[i]]
        # 状态从i-1个花放j-k个位置转移来
        for k in range(a[i] + 1):
            if j - k >= 0:
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod
print(dp[n][m] % mod)

这题有两个大坑！首先就是不是所有花都必须要放上去，然后是a[i]可以是0。

合唱队形

https://www.lanqiao.cn/problems/742/learning/

最长递增子序列

其他答案求LiS的dp都感觉不太对，所求的dp[i]并不是序列前i个数的最长子序列。这个地方折磨了我好久。

这题就是分别找出从左往右和从右往左的最长递增子序列，然后再操作就好了。

n = int(input())
h = list(map(int, input().split()))
dp = [[1 for __ in range(n)] for _ in range(2)]
# dp[0][0] = 1
# dp[1][-1] = 1

for i in range(1, n):
    idx_dp, idx_h = 0, 0
    for j in range(i):
        if h[i] > h[j]:
            dp[0][i] = max(dp[0][i], dp[0][j] + 1)
    ii = n - 1 - i
    for j in range(n - 1, ii, -1):
        if h[ii] > h[j]:
            dp[1][ii] = max(dp[1][ii], dp[1][j] + 1)
for i in range(1, n):
    if dp[0][i] < dp[0][i - 1]:
        dp[0][i] = dp[0][i - 1]
    if dp[1][n - 1 - i] < dp[1][n - i]:
        dp[1][n - 1 - i] = dp[1][n - i]
# print(dp[0])
# print(dp[1])
res = n - dp[1][0]
for i in range(n - 1):
    res = min(res, n - dp[0][i] - dp[1][i + 1])
res = min(res, n - dp[1][-1])
print(res)

游园安排

有点难，参考了题解。

import bisect

s = input()
names = [" "]
pos = 0
for i in range(1, len(s)):
    if s[i].isupper():
        names.append(s[pos:i])
        pos = i
names.append(s[pos:])
n = len(names)
visitors = [names[0], names[1]]
path = [-1] * n  # path[i]=j记录第i个人的上一个人应该是j，最后从最后一个往回找
record = [-1,
          1]  # record[i]=j，记录visitors[i]这个name在names里的下标是j，record[i-1]=jj，path[j]=jj，在path里可以找到names[j]的前一个是names[jj]
for i in range(2, n):
    name = names[i]
    pos = bisect.bisect_left(visitors, name)
    if pos == len(visitors):
        visitors.append(name)
        record.append(i)
        path[i] = record[-2]
    else:
        visitors[pos] = name
        record[pos] = i
        path[i] = record[pos - 1]
# print(path)
# print(record)
res = []
p = record[-1]
while path[p] != -1:
    res.append(names[p])
    p = path[p]
res.append(names[p])
print("".join(res[::-1]))