python实现DP经典问题

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最多能够摘到多少颗花生。

1.gif

输入格式

第一行是一个整数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)])

整数二分步骤：
1.找一个区间[L，R]，使得答案一定在该区间中
2.找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间；
4.如果更新方式写的是R=Mid，则不用做任何处理；如果更新方式写的是L=Mid，则需要在计算Mid时加上1。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,793评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,567评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,342评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,825评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,814评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,680评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,033评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,687评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,175评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,668评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,775评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,419评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,020评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,206评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,092评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,510评论 2赞 343