线性DP与真题

【题目描述】

给定一个长度为 n 数组 A 和一个长度为 m 的数组 B。请你求出它们的最长公共子序列长度为多少。

【输入描述】

输入第一行包含两个整数 n、m。第二行包含 n 个整数 ai第三行包含 m 个整数 bi 1≤n, m≤10^3, 1≤ai, bi≤10^9。

【输出描述】

输出一行整数表示答案。

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如X = {A, B, C, B, D, A, B}、它的子序列有 {A, B, C, B, A}、{A, B,D}、{B, C, D, B} 等。
给定两个序列 X 和 Y当另一序列 Z 既是 X 的子序列又是 Y 的子序列时称 Z 是序列 X 和 Y 的公共子序列。
最长公共子序列是长度最长的子序列。
暴力法先找出 A 的所有子序列然后一一验证是否为 Y 的子序列。
如果 A 有 m 个元素那么 A 有 2^m 个子序列B 有 n 个元素总复杂度大于 O(n2^m)。

【动态规划】

dp[i][j]序列 Ai(a1~ai) 和 Bj(b1~bj)的最长公共子序列的长度。答案: dp[n][m]

分解为 2 种情况

1当 ai=bj 时已求得 Ai-1 和 Bj-1 的最长公共子序列在其尾部加上 ai 或 bj 即可得到 Ai 和 Bj 的最长公共子序列。状态转移方程dp[i][j]=dp[i-1][j-1]+1

2当 ai≠bj 时求解两个子问题Ai-1 和 Bj 的最长公共子序列Ai 和 Bj-1 的最长公共子序列。取最大值状态转移方程dp[i][j]=max{dp[i][j-1], dp[i-1][j]}

3复杂度 O(nm)

上述解释通俗易懂啊

【用交替滚动数组】

1当 ai=bj 时状态转移方程dp[i][j]=dp[i-1][j-1]+1

2当 ai≠bj 时状态转移方程dp[i][j]=max{dp[i][j-1], dp[i-1][j]}

n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(2)]    #注意这里是m
now=0
old=1
for i in range(1,n+1):
    now,old=old,now
    for j in range(1,m+1):
        dp[now][j]=max(dp[now][j-1],dp[old][j])
        if a[i]==b[j]:
            dp[now][j]=max(dp[now][j],dp[old][j-1]+1)
print(dp[now][m])

三、最长递增子序列

1、蓝桥骑士lanqiaoOJ题号1188

【题目描述】

小明是蓝桥王国的骑士他喜欢不断突破自我。这天蓝桥国王给他安排了 N 个对手他们的战力值分别为 a1, a2, ..., an且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战也可以选择避战。身为高傲的骑士小明从不走回头路且只愿意挑战战力值越来越高的对手。请你算算小明最多会挑战多少名对手。

【输入描述】

第一行是整数 N表示对手的个数第二行是 N 个整数 a1, a2, ..., an表示对手战力值。1 ≤ N ≤ 3×10^5

【输出描述】

输出一行整数表示答案。

【分析】

给定一个长度为 n 的数组找出一个最长的单调递增子序列。

例序列 A={5, 6, 7, 4, 2, 8, 3}它最长的单调递增子序列为{5, 6, 7, 8}长度为 4。

定义状态dp[i]表示以第 i 个数为结尾的最长递增子序列的长度。

状态转移方程dp[i] = max{dp[j]} + 10<j<iAj<Ai

答案max{dp[i]}

复杂度j 在 0~i 之间滑动复杂度 O(n)i 的变动范围也是 O(n) 的总复杂度 O(n^2)。

动态规划复杂度 O(n^2)

本题 n<=3×10^5DP 代码提交到 OJ 会超时。

DP 不是 LIS 问题的最优解法有复杂度 O(nlogn) 的非DP解法

这题就此打住。

四、编辑距离

1、字符串转换lanqiaoOJ题号1507

【题目描述】

给定两个单词 A 和 B计算出将 A 转换为 B 所需的最小操作数。一个单词允许进行以下 3 种操作 1插入一个字符2删除一个字符3替换一个字符。

【输入描述】

输入第一行包含一个字符串 S。输入第二行包含一个字符串 T。1<=|S|, IT|<=2×10^3保证 S、T 只包含小写字母。

【输出描述】

输出一个整数表示答案。

【分析】

把长度 m 的 A 存储在数组 a[1]~a[m]长度为 n 的 B 存储在 b[1]~b[n]不用 a[0] 和 b[0]。
定义状态 dpdp[i][j] 表示 A 的前 i 个字符转换 B 的前 j 个字符所需要的操作步骤
dp[m][n] 就是答案

下图是 A="abcf"B="bcfe" 的状态转移矩阵。

状态转移方程

1若 a[i] = b[j]则 dp[i][j] = dp[i-1][j-1]。例如图中 dp[2][1] 处的箭头。

2其他情况dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1。例如图中 dp[4][2] 处的箭头。dp[i][j] 是它左、左上、上的三个值中的最小值加1分别对应以下操作

dp[i-1][j]+1删除将 A 的最后字符删除
dp[i][j-1]+1插入在 B 的最后插入A的最后字符
dp[i-1][j-1]+1替换将 B 的最后一个字符替换为 A 的最后一个字符。

复杂度0(mn)。

a=input()
a=' '+a         #a[0]不用
b=input()
b=' '+b
m=len(a)-1
n=len(b)-1
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    dp[i][0]=i
for j in range(1,n+1):
    dp[0][j]=j
for i in range(1,m+1):
    for j in range(1,n+1):
        if a[i]==b[j]:
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1
print(dp[m][n])

五、网络图上的DP

1、过河卒lanqiaoOJ题号755

【题目描述】

棋盘上 A 点有一个过河卒需要走到目标 B 点。卒行走的规则可以向下、或者向右。同时在棋盘上 C 点有一个对方的马该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为 “马拦过河卒”。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数假设马的位置是固定不动的并不是卒走一步马走一步。棋盘用坐标表示A 点 (0, 0)、B 点 (n,m)同样马的位置坐标是需要给出的。1<=n, m<=200<=马的坐标<=20。

【输入格式】

一行四个正整数表示 B 点坐标和马的坐标。

【输出格式】

一个整数表示所有的路径条数。

统计路径条数看起来是个搜索题可以用 DFS 求解。把马的控制点标记为不走绕过它们。不过用 DFS 搜索的路径数量是天文数字肯定超时。
在小学上过奥数的都知道这题应该用 “标数法”就是在每个坐标点上记录能走的路径条数。
标数法实际上就是DP的递推。

【DP】

定义状态 dp[][]dp[i][j] 表示卒走到坐标 (i, j) 时能走的路径条数。
如果不考虑马的控制点有dp[i][j]=dp[i-1][j] + dp[i][j-1]
也就是 (i, j) 点的路径条数等于它上面和左边的路径条数之和。这就是小学奥数的 “标数法” 的原理。
本题的限制条件是马的控制点只要令控制点的 dp[i][j]=0 即可即这个点上无路径。

小技巧把坐标加2防止马的控制点越界。

dp=[[0]*25 for i in range(25)]
s=[[0]*25 for i in range(25)]
bx,by,mx,my=map(int,input().split())
bx+=2
by+=2
mx+=2
my+=2
dp[2][1]=1
s[mx][my]=1
s[mx-2][my-1]=1
s[mx-2][my+1]=1
s[mx+2][my-1]=1
s[mx+2][my+1]=1
s[mx-1][my-2]=1
s[mx-1][my+2]=1
s[mx+1][my-2]=1
s[mx+1][my+2]=1
for i in range(2,bx+1):
    for j in range(2,by+1):
        if s[i][j]==1:
            dp[i][j]=0
        else:
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(dp[bx][by])

这类题其实是最好做了。

六、其他例题

1、排列数2019年国赛lanqiaoOJ题号240

【题目描述】

在一个排列中一个折点是指排列中的一个元素它同时小于两边的元素或者同时大于两边的元素。对于一个 1~n 的排列如果可以将这个排列中包含 t 个折点则它称为一个 t+1 单调序列。例如排列 (1, 4, 2, 3) 是一个 3 单调序列其中 4 和 2 都是折点。给定 n 和 k请问 1~n 的所有排列中有多少个 k 单调队列?

【输入描述】

输入一行包含两个整数 n, k (1<=k<=n<=500)。

【输出描述】

输出一个整数表示答案。答案可能很大你可需要输出满足条件的排列数量除以 123456 的余数即可。

1暴力法

20% 的测试 1<=k<=n<=10

暴力法对所有排列进行检查判断是否为 k 单调队列。

from itertools import *
n,k=map(int,input().split())
nums=[i for i in range(1,n+1)]      #1~n
cnt=0
for num in permutations(nums):      #检查每个排列
    tmp=0
    for i in range(n-2):
        if num[i+1]>num[i+2] and num[i+1]>num[i]:
            tmp+=1                  #凸折点
        elif num[i+1]<num[i+2] and num[i+1]<num[i]:
            tmp+=1                  #凹折点
    if tmp==k-1:
        cnt+=1
print(cnt%123456)

2DP

定义dp[][]dp[i][j] 表示序列包含 1~i且排列为 j 单调队列的方案数也就是含有 j-1 个折点的方案数。

答案: dp[n][k]

状态转移方程

从 dp[i-1][] 递推到 dp[i][]把 i 插入到 1~i-1 的一个排列中折点数量的变化

dp[i][j] = dp[i-1][j]*j + dp[i-1][j-1]*2 + dp[i-1][j-2]*(i-j)

怎么退出状态转移方程是关键

N=520
dp=[[0]*N for i in range(N)]
n,k=map(int,input().split())
dp[1][1]=1
dp[2][1]=2
for i in range(3,n+1):
    ki=min(k,i)
    for j in range(1,ki+1):
        dp[i][j]+=dp[i-1][j]*j+dp[i-1][j-1]*2
        if j>1:
            dp[i][j]+=dp[i-1][j-2]*(i-j)
print(dp[n][k]%123456)

2、砝码称重2021年省赛lanqiaoOJ题号1447

【题目描述】

你有一架天平和 N 个砝码这 N 个砝码重量依次是 W1, W2, ······, WN。请你计算一共可以称出多少种不同的重量注意砝码可以放在天平两边。

【输入描述】

输入的第一行包含一个整数 N。第二行包含 N 个整数: W1, W2, W3, ······, WN。

【输出描述】

输出一个整数代表答案。对于所有评测用例1≤N≤100 N 个砝码总重不超过 100000。

【DP】

建模给定 n 个正整数从中选出若个数字组合每个数字可以加或者减最终能得到多少种正整数结果。

DP状态定义dp(i, j) 表示前 i 个数字选择若干个加或者减能否获得和为 j。

DP状态转移方程dp(i, j)=dp(i-1, j)|dp(i-1, j-wi)|dp(i-1, j+wi)

状态转移方程中有三种情况

dp(i-1, j)不用第 i 个数字和为 j

dp(i-1, j-wi)用第 i 个数字且做减法等价于用 i-1 个数字实现 j-wi;

dp(i-1, j+wi)用第 i 个数字且做加法等价于用 i-1 个数字实现 j+wi;

这一题也可以直接模拟并且用 set 判重。

n=int(input())
w=list(map(int,input().split()))
ans=set()
ans.add(w[0])
for i in w[1:]:
    for j in ans.copy():
        ans.add(i)
        ans.add(j+i)
        if j-i!=0:
            ans.add(abs(j-i))
print(len(ans))

3、数字三角形2020年省赛lanqiaoOJ题号505

【题目描述】

图中给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外向左下走的次数与向右下走的次数相差不能超过 1。

【输入格式】

输入的第一行包含一个整数 N1＜N <= 100表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

【输出格式】

输出一个整数表示答案。

【输入】

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

【输出】

27

本题要求向左走的次数与向右走的次数差值不超过 1当到达最后一层时一定是落在中间位置。

如果层数是奇数最后一层落在正中间元素上

如果层数是偶数最后一层落在第 N/2 或第 N/2+1 个元素上。

定义状态 dp[][]dp[i][j] 表示从顶部到第 i 层横向第 j 个数最大路径和。它只能从上一层的左边或右边转移而来。

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
#数组a[][]同时当成dp[][]用
for i in range(1,n):
    for j in range(0,i+1):
        if j==0:
            a[i][j]+=a[i-1][j]      #最左边元素
        elif j==i:
            a[i][j]+=a[i-1][j-1]    #最右边元素
        else:
            a[i][j]+=max(a[i-1][j-1:j+1])
if n&1:
    print(a[-1][n//2])
else:
    print(max(a[-1][n//2-1],a[-1][n//2]))

补充练习题