目录
题目描述
给定一个长度为 N 数组 a 和一个长度为 M 的数组 b。
请你求出它们的最长公共子序列长度为多少。
最长公共子序列（Longest Common Subsequence，LCS）：一个给定序列的子序列，是在该序列中删去若干元素后得到的序列。例如：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的公共子序列。最长公共子序列是长度最长的子序列。
输入描述
输入第一行包含两个整数 N,M，分别表示数组 a 和 b 的长度。
第二行包含 N 个整数a1,a2,...,an。
第三行包含 M 个整数 b1,b2,...,bn。
1≤N,M≤103，1≤ai,bi≤10^9。
输出描述
输出一行整数表示答案。
样例输入
5 6 1 2 3 4 5 2 3 2 1 4 5样例输出
4
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[[0 for i in range(1050)]for j in range(1050)]
for i in range(1,n+1):
for j in range(1,m+1):
if a[i-1]==b[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[n][m])
题目描述
小明是蓝桥王国的骑士，他喜欢不断突破自我。
这天蓝桥国王给他安排了 N 个对手，他们的战力值分别为a1,a2,...,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。
身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 N，表示对手的个数。
第二行包含 N 个整数a1,a2,...,an，分别表示对手的战力值。
1≤N≤3×105，1≤ai≤10^9。
输出描述
输出仅一行包含一个整数表示答案。
样例输入
6 1 4 2 2 5 6样例输出
4
N=10005
n=int(input())
dp=[0 for i in range(N)]
a=list(map(int,input().split()))
ans=0
dp[0]=1
for i in range(1,n):
maxn=0
for j in range(i):
if dp[j]>maxn and a[j]<a[i]:
maxn=dp[j]
dp[i]=maxn+1
ans=max(ans,dp[i])
print(ans)
题目描述
小蓝拥有两个字符串 S,T。他希望通过如下操作使得字符 S 转换为字符串 T。
操作有一下三种：
- 删除一个字符。
- 插入一个字符。
- 将一个字符改为另一个字符。
问最少需要操作多少次才可以使得字符串 S 转换为字符串 T。
输入描述
输入第一行包含一个字符串 S。
输入第二行包含一个字符串 T。
1≤∣S∣,∣T∣≤2×10^3，保证 S、T 只包含小写字母。
输出描述
输出一个整数表示答案。
输入输出样例
示例 1
输入
abc aa输出
2
a=input()
b=input()
dp=[[0 for i in range(2005)]for j in range(2005)]
m=len(a)
n=len(b)
for i in range(1,m+1):
for j in range(1,n+1):
if a[i-1]==b[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
print(dp[m][n])
题目描述
有一个箱子容量为 V（正整数0≤V≤20000），同时有n 个物品（0≤n≤30），每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述
输入第一行，一个整数，表示箱子容量。
第二行，一个整数 n，表示有 n 个物品。
接下来n 行，分别表示这 n 个物品的各自体积。
输出描述
输出一行，表示箱子剩余空间。
样例输入
24 6 8 3 12 7 9 7样例输出
0
n=int(input())
m=int(input())
w=[]
for i in range(m):
w.append(int(input()))
dp=[0 for i in range(20005)]
for i in range(m):
for j in range(n,w[i]-1,-1):
dp[j]=max(dp[j],dp[j-w[i]]+w[i])
print(n-dp[n])
题目描述
如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
例如上图 CC 点上的马可以控制 9 个点（图中的 1，P2，⋯P8 和 CC）。卒不能通过对方马的控制点。
棋盘用坐标表示，A 点（0，0）、B 点（n,m）(
)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。。
输入描述
一行四个正整数，分别表示 B 点坐标和马的坐标。
输出描述
一个整数，表示所有的路径条数。
输入输出样例
示例 1
输入
6 6 3 3输出
6
n,m,a,b=map(int,input().split())
dir=[(1,2),(-1,2),(-1,-2),(1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
vis=[]
s=[(a,b)]
for i in range(8):
x=a+dir[i][0]
y=b+dir[i][1]
if x>0 and y>0:
s.append((x,y))
dp=[[0 for i in range(25)]for j in range(25)]
dp[0][0]=1
for i in range(n+1):
for j in range(m+1):
if (i,j) not in s:
if i==0:
dp[i][j]=1
if j==0:
dp[i][j]=1
if i>0 and j>0:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(dp[n][m])