动态规划类的一些整理

1. 01背包问题求最大价值

关键: 1.优化成一维后j要从后面往前遍历，保证使用的是i-1行的数据

N = 1010
f = [0]*N
v = [0]*N
w = [0]*N

def dp():
    for i in range(1,n+1):
        for j in range(m,v[i]-1,-1):
            f[j] = max(f[j],f[j-v[i]]+w[i])

    return f[m]

n,m = map(int,input().split())
for i in range(1,n+1):
    a,b = map(int,input().split())
    v[i] = a
    w[i] = b

print(dp())

相关题目：423.采药 01 背包求最大价值模板题

2. 变种01背包求最大价值问题 - 装箱问题

装箱问题我们只需要将体积也看作是物品的一个价值，求出箱子的最大价值（也就是箱子能够装下的最大的体积），然后再用箱子的容积减去箱子的“最大价值”即为答案所求。

V  =20010
f = [0]*V
N = 40
w = [0]*N
v = [0]*N

def dp():
    for i in range(1,n+1):
        for j in range(m,v[i]-1,-1):
            f[j] = max(f[j],f[j-v[i]]+w[i])

    return m-f[m]

m = int(input())
n = int(input())
for i in range(1,n+1):
    a = int(input())
    v[i] = w[i] = a

print(dp())

3.完全背包问题

完全背包问题关键点与01背包不同的是完全背包对于物品的选择可以多次选择，所以在遍历j时，我们应该从前往后遍历，这样保证我们使用的数据来自当前层。

N = 1010
v = [0]*N
w = [0]*N
f = [0]*N

def dp():
    for i in range(1,n+1):
        for j in range(v[i],m+1):
            f[j] = max(f[j],f[j-v[i]]+w[i])
    return f[m]

n,m = map(int,input().split())
for i in range(1,n+1):
    a,b = map(int,input().split())
    v[i] = a
    w[i] = b

print(dp())

4.完全背包求方案数 整数划分

这里f数组所存的状态属性是方案数，所以我们在一开始时记得把f[0] = 1 即可

mod = 1e9+7
N = 1010
f = [0]*N
n = int(input())

def dp():
    f[0] = 1
    for i in range(1,n+1):
        for j in range(i,n+1):
            f[j]  = (f[j]+f[j-i])%mod
    return int(f[n])

print(dp())

4.1 完全背包求方案数 买书

有了上一题的思路，这一道题就迎刃而解了

N = 1010
f =[0]*N
a = [0,10,20,50,100]

def dp():
    f[0] = 1
    for i in range(1,5):
        for j in range(a[i],n+1):
            f[j] = f[j]+f[j-a[i]]

    return f[n]

n = int(input())
print(dp())

5. 01背包求方案数 数字组合

这里我们只需要将给出的数字当作物品的体积即可，题目就变成了求出恰好装满背包体积m的组合方案数

M = 10010
N = 110
f = [0]*M
a = [0]*N

def dp():
    f[0] = 1
    for i in range(1,n+1):
        for j in range(m,a[i]-1,-1):
            f[j] = f[j]+f[j-a[i]]

    return f[m]

n,m = map(int,input().split())
a[1:] = list(map(int,input().split()))
print(dp())

6.多重背包问题

N = 110
f = [0]*N
w = [0]*N
v = [0]*N
s = [0]*N

def dp():
    for i in range(1,n+1):
        for j in range(m,v[i]-1,-1):
            for k in range(s[i]+1):
                if j>=k*v[i]:
                    f[j] = max(f[j],f[j-k*v[i]]+w[i]*k)

    return f[m]

n,m = map(int,input().split())
for i in range(1,n+1):
    a,b,c = map(int,input().split())
    v[i] = a
    w[i] = b
    s[i] = c
print(dp())

7.01背包价值最大方案数 背包问题求方案数

思路和01背包求最大价值大致一致，只需要再多加一个g数组来记录方案数即可。

注意：这里求的是最大价值方案数 与之前的求方案数有一点不同

N = 1010
mod = 1e9+7
v = [0]*N
w = [0]*N
f = [0]*N
g = [0]*N

def dp():
    g[0] = 1
    for i in range(1,n+1):
        for j in range(m,v[i]-1,-1):
            temp = max(f[j],f[j-v[i]]+w[i])
            c = 0
            if temp==f[j]:c = (c+g[j])%mod
            if temp==f[j-v[i]]+w[i]: c = (c+g[j-v[i]])%mod
            g[j] = c
            f[j] = temp
    res = 0
    for i in range(m+1):
        if f[i]==f[m]:
            res+=g[i]

    return int(res)

n,m = map(int,input().split())
for i in range(1,n+1):
    a,b = map(int,input().split())
    v[i] =a
    w[i] = b

print(dp())

7.最长上升子序列

f[i] 表示以i结尾的最长上升子序列 故最终返回的是整个f数组里面最大值。

N = 1010
f = [0]*N
a = [0]*N
def dp():
    for i in range(1,n+1):
        f[i] = 1
        for j in range(1,i):
            if a[j]<a[i]:
                f[i] = max(f[i],f[j]+1)

    return max(f)

n = int(input())
a[1:] = list(map(int,input().split()))
print(dp())

8.最长上升子序列和

最长上升子序列和与最长上升子序列不同的就在于一个存的是整个数的和，一个存的是个数，所以只需要在状态转移时加上数组的值而不是单纯加1即可

N = 1010
f = [0]*N
a = [0]*N

def dp():
    for i in range(1,n+1):
        f[i] = a[i]
        for j in range(1,i):
            if a[j]<a[i]:
                f[i] = max(f[i],f[j]+a[i])

    return max(f)

n = int(input())
a[1:] = list(map(int,input().split()))
print(dp())

9.最长公共子序列

N = 1010
M = 1010
f = [[0]*M for i in range(N)]
def dp():
    for i in range(1,n+1):
        for j in range(1,m+1):
            if a[i]==b[j]:
                f[i][j] = f[i-1][j-1]+1
            else:
                f[i][j] = max(f[i-1][j],f[i][j-1])

    return f[n][m]

n,m = map(int,input().split())
a = ' '+input()
b = ' '+input()
print(dp())

10.最长公共子串

最长公共子串与最长公共子序列唯一不同的就是子序列可以分散，而子串必须是连续的一段。唯一不同点就在于如果两个字符不相同的话，就直接将f[i][j]置为0

N = 1010
M = 1010
f = [[0]*M for i in range(N)]
def dp():
    res = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if a[i]==b[j]:
                f[i][j] = f[i-1][j-1]+1
                res = max(res,f[i][j)
            else:
                f[i][j] = 0

    return res

n,m = map(int,input().split())
a = ' '+input()
b = ' '+input()
print(dp())

11.最长公共上升子序列

N = 3010
f = [[0]*N for i in range(N)] 
a = [0]*N
b = [0]*N
#f[i,j]考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案 属性：长度max

def dp():
    for i in range(1,n+1):
        ms = 1
        for j in range(1,n+1):
            f[i][j] = f[i-1][j]
            if a[i]==b[j]:f[i][j] = max(f[i][j],ms)
            if a[i]>b[j]:ms = max(ms,f[i-1][j]+1)
    res = 0
    for i in range(1,n+1):
        res = max(res,f[n][i])

    return res

n = int(input())
a[1:] = list(map(int,input().split()))
b[1:] = list(map(int,input().split()))
print(dp())