一、小明的背包1
试题链接：https://www.lanqiao.cn/problems/1174/learning/
问题描述
输入实例
5 20
1 6
2 5
3 8
5 15
3 3 输出示例
37问题分析
这里我们要创建一个DP表，DP（i，j）表示处理到第i个物品时消耗j体积。这样我们在输入数据时可以直接进行操作。对于每一个dp[i][j]我们都可以转化为求其子问题的最优解，即返回到上一次dp[i-1]，我们需要注意一个特殊的值dp[i-1][j-w]（w为第i个数的体积),我们可以由dp[i-1][j-w]+v （v为第i个物品的价值)到达dp[i][j]，也可以由dp[i-1][j]直接到dp[i][j]，这里就分成了两种情况，即要么选第i个物品，要么不选第i个物品。这样就形成一个dp表，我们只需要求出其中的最大值即可。
PS：对dp表还可以进行一个空间优化，每一个dp[i][j]只和dp[i-1]有关，所以我们只需要两个一维列表即可，每操作完一个物品，就将dp0替换成dp1
代码示例
N,V=map(int,input().split())
dp=[[0]*(V+1) for _ in range(N+1)]
ans=0
for i in range(1,N+1):
w,v=map(int,input().split())
for j in range(V+1):
if j-w>=0:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
else:
dp[i][j]=dp[i-1][j]
ans=max(ans,dp[i][j])
print(ans)
空间优化后的代码
N,V=map(int,input().split())
dp0=[0]*(V+1)
dp1=[0]*(V+1)
ans=0
for i in range(1,N+1):
w,v=map(int,input().split())
for j in range(V+1):
if j-w>=0:
dp1[j]=max(dp0[j],dp0[j-w]+v)
else:
dp1[j]=dp0[j]
ans=max(ans,dp1[j])
dp0=dp1.copy()
print(ans)
二、2022
试题链接：https://www.lanqiao.cn/problems/2186/learning/
问题描述
问题分析
这是一道DP问题，要三个参数，dp[i][j][k]代表判断到第i个数，选择了其中j个数，和为k共有多少种情况。
对于dp[i][j][k]可以分两种情况：①k>=i；这时dp[i][j][k]=dp[i-1][j-1][k-i]+dp[i-1][j][k]（即选择i或不选) ②k<i；这时dp[i][j][k]=dp[i-1][j][k]（想加也加不进去）
初始条件为dp[i][0][0]=1，注意dp[0][0][0]也为1，否则dp[1][1][1]==0
代码示例
V=2022
n=2022
dp=[[[0]*2023 for _ in range(11)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
dp[i][0][0]=1
for j in range(1,11):
for k in range(1,2023):
if k>=i:
dp[i][j][k]=dp[i-1][j-1][k-i]+dp[i-1][j][k]
else:
dp[i][j][k]=dp[i-1][j][k]
print(dp[2022][10][2022])
#379187662194355221三、过河卒
试题链接：https://www.lanqiao.cn/problems/755/learning/
输入示例
6 6 3 3输出示例
6
问题分析
对于每一个点（i，j），从起点开始到该点的不同路径为dp[i][j]，由题意可得只能从该点左边或上面到达该点，所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。注意不要出界且部分点不能走即可。
代码示例
a,b,c,d=map(int,input().split())
dp=[[0]*(b+1) for _ in range(a+1)]
dp[0][0]=1
dp[c][d]=-1
he=[-2,-2,-1,-1,1,1,2,2]
sh=[-1,1,-2,2,-2,2,-1,1]
for _ in range(8):
i=c+he[_]
j=d+sh[_]
if i>=0 and j>=0:
dp[i][j]=-1
for i in range(a+1):
for j in range(b+1):
if dp[i][j]==-1:
dp[i][j]=0
else:
if i>0:
dp[i][j]+=dp[i-1][j]
if j>0:
dp[i][j]+=dp[i][j-1]
print(dp[a][b])
