title: DP经典问题的python实现 date: 2020-03-26 22:13:26 categories: 算法 tags: [python, DP]
01背包
有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000 0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
普通代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
,m
=map(int,input().split
())
v
=[0 for i
in range(0,n
+1)]
w
=[0 for i
in range(0,n
+1)]
dp
=[[0 for i
in range(0,m
+1)] for i
in range(0,n
+1)]
for i
in range(0,n
):
v
[i
],w
[i
]=map(int,input().split
())
for i
in range(0,n
):
for j
in range(0,m
+1):
dp
[i
][j
]=dp
[i
-1][j
]
if j
>=v
[i
]:
dp
[i
][j
]=max(dp
[i
][j
],dp
[i
-1][j
-v
[i
]]+w
[i
])
print(dp
[n
-1][m
])
优化代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
,m
=map(int,input().split
())
v
=[0 for i
in range(0,n
+1)]
w
=[0 for i
in range(0,n
+1)]
dp
=[0 for i
in range(0,m
+1)]
for i
in range(0,n
):
v
[i
],w
[i
]=map(int,input().split
())
for i
in range(0,n
):
for j
in range(m
,v
[i
]-1,-1):
dp
[j
]=max(dp
[j
],dp
[j
-v
[i
]]+w
[i
])
print(dp
[m
])
完全背包
有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 ii 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000 0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
基本代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
,m
=map(int,input().split
())
v
=[0 for i
in range(0,n
+1)]
w
=[0 for i
in range(0,n
+1)]
dp
=[[0 for i
in range(0,m
+1)] for i
in range(0,n
+1)]
for i
in range(0,n
):
v
[i
],w
[i
]=map(int,input().split
())
for i
in range(0,n
):
for j
in range(0,m
+1):
dp
[i
][j
]=dp
[i
-1][j
]
if j
>=v
[i
]:
dp
[i
][j
]=max(dp
[i
-1][j
],dp
[i
][j
-v
[i
]]+w
[i
])
print(dp
[n
-1][m
])
优化代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
,m
=map(int,input().split
())
v
=[0 for i
in range(0,n
+1)]
w
=[0 for i
in range(0,n
+1)]
dp
=[0 for i
in range(0,m
+1)]
for i
in range(0,n
):
v
[i
],w
[i
]=map(int,input().split
())
for i
in range(0,n
):
for j
in range(v
[i
],m
+1):
dp
[j
]=max(dp
[j
],dp
[j
-v
[i
]]+w
[i
])
print(dp
[m
])
石子合并
设有N堆石子排成一排，其编号为1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；
如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数N表示石子的堆数N。
第二行N个数，表示每堆石子的质量(均不超过1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤3001≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
=int(input())
a
=list(IA
())
s
=[0 for i
in range(0,n
+1)]
dp
=[[0 for i
in range(0,n
+1)] for i
in range(0,n
+1)]
s
[0]=0
for i
in range(0,n
):
s
[i
+1]=s
[i
+1-1]+a
[i
]
for le
in range(2,n
+1):
for i
in range(1,n
+1):
j
=i
+le
-1
if j
>n
:break
dp
[i
][j
]=1e18
for k
in range(i
,j
):
dp
[i
][j
]=min(dp
[i
][j
],dp
[i
][k
]+dp
[k
+1][j
]+s
[j
]-s
[i
-1])
print(dp
[1][n
])
最长公共子序列
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数N和M。
第二行包含一个长度为N的字符串，表示字符串A。
第三行包含一个长度为M的字符串，表示字符串B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001≤N≤1000,
输入样例：
4 5
acbd
abedc
输出样例：
3
代码
import sys
,math
sys
.setrecursionlimit
(10**9)
from collections
import defaultdict
IA
= lambda: map(int,input().split
())
IAS
= lambda: map(str,input().split
())
n
,m
=IA
()
s1
=str(input())
s2
=str(input())
dp
=[[0 for i
in range(0,m
+1)] for i
in range(0,n
+1)]
for i
in range(1,n
+1):
for j
in range(1,m
+1):
dp
[i
][j
]=max(dp
[i
-1][j
],dp
[i
][j
-1])
if s1
[i
-1]==s2
[j
-1]:
dp
[i
][j
]=max(dp
[i
][j
],dp
[i
-1][j
-1]+1)
print(dp
[n
][m
])
最长上升子序列
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001≤N≤1000， −109≤数列中的数≤109−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
代码
o(n^2)
IA
=lambda:map(int,input().split
())
n
=int(input())
a
=list(IA
())
dp
=[0 for i
in range(0,n
)]
ans
=0
for i
in range(0,n
):
dp
[i
]=1
for j
in range(0,i
):
if a
[i
]>a
[j
]:
dp
[i
]=max(dp
[i
],dp
[j
]+1)
ans
=max(dp
[i
],ans
)
print(ans
)
O(n*logn)
IA
=lambda:map(int,input().split
())
n
=int(input())
a
=list(IA
())
dp
=[0 for i
in range(0,n
)]
def two_find(l
,r
,val
):
while l
<r
:
mid
=l
+r
>>1
if dp
[mid
]>=val
:
r
=mid
else:
l
=mid
+1
return r
cnt
=0
dp
[cnt
]=a
[0]
cnt
+=1
for i
in range(1,n
):
if a
[i
]>dp
[cnt
-1]:
dp
[cnt
]=a
[i
]
cnt
+=1
else:
dp
[two_find
(0,cnt
,a
[i
])]=a
[i
]
print(cnt
)
摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100 1≤R,C≤100 0≤M≤10000≤M≤1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16
代码
朴素做法
IA
=lambda:map(int,input().split
())
T
=int(input())
for t
in range(0,T
):
n
,m
=IA
()
mp
=[[0 for j
in range(0,m
+1)] for i
in range(0,n
+1)]
dp
=[[0 for j
in range(0,m
+1)] for i
in range(0,n
+1)]
for i
in range(1,n
+1):
mp
[i
][1:]=list(IA
())
for i
in range(1,n
+1):
for j
in range(1,m
+1):
dp
[i
][j
]=max(dp
[i
-1][j
],dp
[i
][j
-1])+mp
[i
][j
]
print(dp
[n
][m
])
等价变化的优化(删掉一维是否可行)
IA
=lambda:map(int,input().split
())
T
=int(input())
for t
in range(0,T
):
n
,m
=IA
()
mp
=[[0 for j
in range(0,m
+1)] for i
in range(0,n
+1)]
dp
=[0 for j
in range(0,m
+1)]
for i
in range(1,n
+1):
mp
[i
][1:]=list(IA
())
for i
in range(1,n
+1):
for j
in range(1,m
+1):
dp
[j
]=max(dp
[j
],dp
[j
-1])+mp
[i
][j
]
print(dp
[m
])
地宫取宝
X 国王有一个地宫宝库，是 n×mn×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 kk 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 kk 件宝贝。
输入格式
第一行 33 个整数，n,m,kn,m,k，含义见题目描述。
接下来 nn 行，每行有 mm 个整数 CiCi 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 kk 个宝贝的行动方案数。
该数字可能很大，输出它对 10000000071000000007 取模的结果。
数据范围
1≤n,m≤501≤n,m≤50, 1≤k≤121≤k≤12, 0≤Ci≤120≤Ci≤12
输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14
代码
IA
=lambda:map(int,input().split
())
n
,m
,k
=IA
()
C
=13
MOD
=1000000007
w
=[[0 for j
in range(0,m
+1)] for i
in range(0,n
+1)]
dp
=[[[[0 for y
in range(C
+1)] for x
in range(k
+1)] for j
in range(m
+1)] for i
in range(n
+1)]
for i
in range(1,n
+1):
w
[i
][1:]=list(IA
())
for j
in range(1,m
+1):
w
[i
][j
]+=1
dp
[1][1][1][w
[1][1]]=1
dp
[1][1][0][0]=1
for i
in range(1,n
+1):
for j
in range(1,m
+1):
if i
==1 and j
==1:continue
for x
in range(0,k
+1):
for y
in range(0,C
+1):
dp
[i
][j
][x
][y
]=(dp
[i
][j
][x
][y
]+dp
[i
-1][j
][x
][y
])%MOD
dp
[i
][j
][x
][y
]=(dp
[i
][j
-1][x
][y
]+dp
[i
][j
][x
][y
])%MOD
if w
[i
][j
]==y
and x
>0:
for t
in range(0,y
):
dp
[i
][j
][x
][y
]=(dp
[i
-1][j
][x
-1][t
]+dp
[i
][j
][x
][y
])%MOD
dp
[i
][j
][x
][y
]=(dp
[i
][j
-1][x
-1][t
]+dp
[i
][j
][x
][y
])%MOD
ans
=0
for i
in range(0,C
+1):
ans
=(ans
+dp
[n
][m
][k
][i
])%MOD
print(ans
)
波动数列
观察这个数列：
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。
栋栋对这种数列很好奇，他想知道长度为 nn 和为 ss 而且后一项总是比前一项增加 aa 或者减少 bb 的整数数列可能有多少种呢？
输入格式
共一行，包含四个整数 n,s,a,bn,s,a,b，含义如前面所述。
输出格式
共一行，包含一个整数，表示满足条件的方案数。
由于这个数很大，请输出方案数除以 100000007100000007 的余数。
数据范围
1≤n≤10001≤n≤1000, −109≤s≤109−109≤s≤109, 1≤a,b≤1061≤a,b≤106
输入样例：
4 10 2 3
输出样例：
2
样例解释
两个满足条件的数列分别是2 4 1 3和7 4 1 -2。
代码
IA
=lambda:map(int,input().split
())
def get_mod(a
,b
):
return (a
%b
+b
)%b
MOD
=100000007
n
,s
,a
,b
=IA
()
dp
=[[0 for j
in range(n
+1)] for i
in range(n
+1)]
dp
[0][0]=1
for i
in range(1,n
):
for j
in range(0,n
):
dp
[i
][j
]=(dp
[i
-1][get_mod
(j
-(n
-i
)*a
,n
)]+dp
[i
-1][get_mod
(j
+(n
-i
)*b
,n
)])%MOD
print(dp
[n
-1][get_mod
(s
,n
)])
