---

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())
    
    #print(mp)
    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())
    
    #print(mp)
    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)])

本文地址：https://blog.csdn.net/sdz20172133/article/details/109217473

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！