动态规划的万能公式（三类题型）

本文主要介绍如何用Python解决动态规划的问题&＃xff0c;在动态规划问题中&＃xff0c;最主要的是找到问题的dp&＃xff0c;即找到状态转移函数&＃xff0c;当你找到了该问题的状态转移函数&＃xff0c;你就成功了一半&＃xff0c;下面我将介绍三类最主要的题型&＃xff0c;对于这三类题型&＃xff0c;分别有着不同的解题公式。

目录

一、斐波那契式

通项公式&＃xff1a;f(n)&＃61;f(n-1)&＃43;f(n-2) 

举例说明

爬楼梯 

骨牌铺方格 

一只小蜜蜂

二、背包问题

通项公式&＃xff1a;f(i,j)&＃61;max(f(i-1,j),f(i-1&＃xff08;或i&＃xff09;,j-w(i))&＃43;v(i)) 

举例说明 

0-1背包问题 

完全背包问题 

矿工问题

三、最长递增子列

通项公式&＃xff1a;f(i,j)&＃61;max(f(i),f(j)&＃43;1)

举例说明 

最长递增子序列

最少拦截系统 

这一类题型基本都有一定的规律&＃xff0c;一般思维是从最后往前推&＃xff0c;找出状态转移函数。 

通项公式&＃xff1a;f(n)&＃61;f(n-1)&＃43;f(n-2) 

def f(n):
if n return
……
if n&＃61;&＃61;t:
return
a,b&＃61;?,?
for i in range(t,n):
sums&＃61;a&＃43;b #该句其实就是动态规划&＃xff08;根据具体情况而改变&＃xff09;&＃xff0c;表示当前的方法数实际上是前面两个方法数之和
a&＃61;b
b&＃61;sums
return sums

举例说明

爬楼梯 

【问题描述】

假设小明住在二楼&＃xff0c;每次回家都需要经过一个有n层台阶的楼梯。

小明每次可以选择一步走一级台阶或者一步走两级台阶。

请计算一下小明从楼下到家一共有多少种走法&＃xff1f;

【输入形式】

整数n&＃xff0c;表示一共有几层台阶

【输出形式】

一行&＃xff0c;表示一共有多少种走法

【样例输入】

10

【样例输出】

89

def Climb(n): #定义的爬楼梯函数
if n<1: #判断是否合法&＃xff0c;台阶不合法&＃xff0c;返回0
return 0
if n&＃61;&＃61;1: #当只有一层台阶时&＃xff0c;一种走法
return 1
if n&＃61;&＃61;2: #当有两层台阶时&＃xff0c;两种走法
return 2
a,b&＃61;1,2 #当台阶数大于3时&＃xff0c;我们发现走法数呈斐波那契排列
sums&＃61;0 #即每一层台阶的走法数等于前两层台阶走法数的和
for i in range(2,n): #这是为什么呢&＃xff0c;因为我们知道&＃xff0c;每次只能走1步或者2步
sums&＃61;a&＃43;b #倒推一下&＃xff0c;我们如何能到达第n级台阶呢&＃xff0c;有两种方法
a&＃61;b #一种是在第9层台阶再走1步&＃xff0c;另一种是在第8层台阶再走2步
b&＃61;sums #而到达第9层也是两种方法&＃xff0c;在第7层走两步或在第8层走一步
return sums #同理所以我们只需要n层前两层走的步数和即可
n&＃61;int(input()) #而前两层又等于前前两层……&＃xff0c;是个斐波那契数列
print(Climb(n))

骨牌铺方格 

【问题描述】

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n&＃61;3时,为2× 3方格&＃xff0c;骨牌的铺放方案有三种,如下图&＃xff1a;

【输入形式】

输入数据由多行组成&＃xff0c;每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0

【输出形式】

对于每个测试实例&＃xff0c;请输出铺放方案的总数&＃xff0c;每个实例的输出占一行。

【样例输入】

1

3

2

【样例输出】

1

3

2

while(1):
def get(n):
if n<1:
return 0
if n&＃61;&＃61;1:
return 1
if n&＃61;&＃61;2:
return 2
a,b&＃61;1,2
for i in range(2,n):
sums&＃61;a&＃43;b
a&＃61;b
b&＃61;sums
return sums
n&＃61;int(input())
print(get(n))

一只小蜜蜂

【问题描述】

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房&＃xff0c;不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中&＃xff0c;蜂房的结构如下所示。

 

【输入形式】

输入数据的第一行是一个整数N,表示测试实例的个数&＃xff0c;然后是N 行数据&＃xff0c;每行包含两个整数a和b(0

【输出形式】

对于每个测试实例&＃xff0c;请输出蜜蜂从蜂房a爬到蜂房b的可能路线数&＃xff0c;每个实例的输出占一行。

【样例输入】

2

1 2

3 6

【样例输出】

1

3

def methods(a,b):
t&＃61;b-a
if t<1:
return 0
if t&＃61;&＃61;1:
return 1
if t&＃61;&＃61;2:
return 2
a,b&＃61;1,2
for i in range(2,t):
sums&＃61;a&＃43;b
a&＃61;b
b&＃61;sums
return sums
N&＃61;int(input())
for i in range(N):
a,b&＃61;map(int,input().split())
print(methods(a,b))
二、背包问题

这类问题细分为0-1背包问题和完全背包问题&＃xff0c;具体差别就在于物品是否有无穷个。

通项公式&＃xff1a;f(i,j)&＃61;max(f(i-1,j),f(i-1&＃xff08;或i&＃xff09;,j-w(i))&＃43;v(i)) 

def f(n,m,v,w):
dp&＃61;[[0 for i in range(m&＃43;1)] for j in range(n&＃43;1)]
for i in range(1,n&＃43;1):
for j in range(1,m&＃43;1):
if j dp[i][j]&＃61;dp[i-1][j]
else: #0-1背包&＃xff08;完全背包&＃xff09;
dp[i][j]&＃61;max(dp[i-1][j],dp[i-1][j-w[i-1]]&＃xff08;或dp[i][j-w[i-1]]&＃xff09;&＃43;v[i-1])
return dp

举例说明 

0-1背包问题 

假设有一个承重力量为C的背包。现有n件物品&＃xff0c;质量分别为w1,w2,……,wn&＃xff0c;价值分别为v1,v2,……vn&＃xff0c;求让背包里装入的物品具有最大价值总和的物品子集。

【问题描述】

假设周末学校要组织跳蚤市场&＃xff0c;某学生准备了电子词典、篮球、网球拍和考研书4件物品进行交易&＃xff0c;要用自己的书包把这些物品带到学校。各个物品的质量w和价值v如表所示&＃xff0c;该学生书包的最大承重量C&＃61;8。我们要解决的问题是帮助该同学找到最合理的搭配方案&＃xff0c;使他能用书包带到学校的物品价值最大。

电子词典 篮球 网球拍 单词书

2 4 5 3

5 4 6 2

【输入样例】

无

【输出样例】

一行&＃xff0c;表示最优方案的物品

【样例输入】

无

【样例输出】

1 3

n&＃61;4
c&＃61;8
w&＃61;[2,4,5,3]
v&＃61;[5,4,6,2]
def bag(n,c,w,v):
results&＃61;[[0 for i in range(c&＃43;1)] for j in range(n&＃43;1)]
for i in range(1,n&＃43;1):
for j in range(1,c&＃43;1):
if j results[i][j]&＃61;results[i-1][j]
else: #在这里最多只能取一个物品&＃xff0c;所以取了当前物品后需要返回上一层
results[i][j]&＃61;max(results[i-1][j],results[i-1][j-w[i-1]]&＃43;v[i-1])
return results
res&＃61;bag(n,c,w,v)
def rec(n,c,w,res):
x&＃61;[0 for i in range(n&＃43;1)]
j&＃61;c
i&＃61;n
while i>&＃61;0:
if res[i][j]>res[i-1][j]:
x[i]&＃61;1
j&＃61;j-w[i]
i&＃61;i-1
for i in range(1&＃43;n):
if x[i]&＃61;&＃61;1:
print(i,end&＃61;&＃39; &＃39;)
rec(n,c,w,res)

完全背包问题 

【问题描述】

对于吃货来说&＃xff0c;过年最幸福的事就是吃了&＃xff0c;没有之一&＃xff01;

但是对于女生来说&＃xff0c;卡路里&＃xff08;热量&＃xff09;是天敌啊&＃xff01;

资深美女湫湫深谙“胖来如山倒&＃xff0c;胖去如抽丝”的道理&＃xff0c;所以她希望你能帮忙制定一个食谱&＃xff0c;能使她吃得开心的同时&＃xff0c;不会制造太多的天敌。

当然&＃xff0c;为了方便你制作食谱&＃xff0c;湫湫给了你每日食物清单&＃xff0c;上面描述了当天她想吃的每种食物能带给她的幸福程度&＃xff0c;以及会增加的卡路里量。

【输入形式】

输入包含多组测试用例。

每组数据以一个整数n开始&＃xff0c;表示每天的食物清单有n种食物。

接下来n行&＃xff0c;每行两个整数a和b&＃xff0c;其中a表示这种食物可以带给湫湫的幸福值&＃xff08;数值越大&＃xff0c;越幸福&＃xff09;&＃xff0c;b表示湫湫吃这种食物会吸收的卡路里量。

最后是一个整数m&＃xff0c;表示湫湫一天吸收的卡路里不能超过m。

【输出形式】

对每份清单&＃xff0c;输出一个整数&＃xff0c;即满足卡路里吸收量的同时&＃xff0c;湫湫可获得的最大幸福值。

【样例输入】

3

3 3

7 7

9 9

10

5

1 1

5 3

10 3

6 8

7 5

6

【样例输出】

10

20

while(1):
def bag(n,m,Happiness,Calorie):
results&＃61;[[0 for i in range(m&＃43;1)] for j in range(n&＃43;1)]
for i in range(1,n&＃43;1):
for j in range(1,m&＃43;1):
if j results[i][j]&＃61;results[i-1][j]
else: #因为物品无穷个&＃xff0c;所有选完后需要在当前层继续选&＃xff0c;不用返回上一层
results[i][j]&＃61;max(results[i-1][j],results[i][j-Calorie[i-1]]&＃43;Happiness[i-1])
return results
n&＃61;int(input())
Happiness&＃61;[]
Calorie&＃61;[]
for i in range(n):
a,b&＃61;map(int,input().split())
Happiness.append(a)
Calorie.append(b)
m&＃61;int(input())
res&＃61;bag(n,m,Happiness,Calorie)
print(res[-1][-1])

矿工问题

【问题描述】

假设某地区有5座钻石矿&＃xff0c;每座钻石矿的钻石储量不同&＃xff0c;根据挖矿难度&＃xff0c;需要参与挖掘的工人数量也不同。假设能够参与挖矿工人的总数是10人&＃xff0c;且每座钻石矿要么全挖&＃xff0c;要么不挖&＃xff0c;不能只派出一部分人挖取一部分矿产。要求用程序求解出&＃xff0c;要想得到尽可能多的钻石&＃xff0c;应该选择挖取哪几座矿产&＃xff1f;

矿产编号 钻石储量 所需工人数量

1 400 5

2 500 5

3 200 3

4 300 4

5 350 3

【输入形式】

无

【输出形式】

一行&＃xff0c;表示获得的最大矿产数

【样例输入】

无

【样例输出】

900

G&＃61;[400,500,200,300,350]
L&＃61;[5,5,3,4,3]
def goldMine(n,m,G,L):
dp&＃61;[[0 for i in range(m&＃43;1)] for j in range(n&＃43;1)]
for i in range(1,n&＃43;1):
for j in range(1,m&＃43;1):
if j dp[i][j]&＃61;dp[i-1][j]
else:
dp[i][j]&＃61;max(dp[i-1][j],dp[i-1][j-L[i-1]]&＃43;G[i-1])
return dp
lst&＃61;goldMine(5,10,G,L)
print(lst[-1][-1])
三、最长递增子列

这个式子主要是求最长递增子列的长度&＃xff0c;而事实上我们还需要求得最长递增子列的元素。 

通项公式&＃xff1a;f(i,j)&＃61;max(f(i),f(j)&＃43;1)

def f(arr):
dp&＃61;[1]*len(arr)
for i in range(len(arr)):
for j in range(i):
if arr[j] dp[i]&＃61;max(dp[i],dp[j]&＃43;1) #状态转移函数
return dp

举例说明 

最长递增子序列

【问题描述】

最长递增子序列问题即给定一个序列&＃xff0c;求解其中最长的递增子序列的长度问题。

先给定序列A{3,1,4,5,9,2,6,5,0}&＃xff0c;求其最长递增子序列。

【输入样例】

一行&＃xff0c;输入A

【输出样例】

一行&＃xff0c;最长递增子序列

【样例输入】

3 1 4 5 9 2 6 5 0

【样例输出】

1 4 5 9

def getdp1(arr): #求得最长递增子列的长度
n&＃61;len(arr)
dp&＃61;[0 for i in range(n)]
for i in range(n):
dp[i]&＃61;1
for j in range(i):
if arr[i]>arr[j]:
dp[i]&＃61;max(dp[i],dp[j]&＃43;1) #动态规划
return dp
def generateLST(arr): #求得最长递增子列的元素
dp&＃61;getdp1(arr)
n&＃61;max(dp)
index&＃61;dp.index(n)
lis&＃61;[0]*n
n-&＃61;1
lis[n]&＃61;arr[index]
for i in range(index-1,-1,-1):
if arr[i] n-&＃61;1
lis[n]&＃61;arr[i]
index&＃61;i
return lis
arr&＃61;[3,1,4,5,9,2,6,5,0]
for i in generateLST(arr):
print(i,end&＃61;&＃39; &＃39;)

最少拦截系统 

【问题描述】

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

【输入形式】

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

【输出形式】

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

【样例输入】

8 389 207 155 300 299 170 158 65

【样例输出】

2

def getdp(arr): #得到每个元素的最长递减序列
n&＃61;len(arr)
dp&＃61;[1]*n #每个元素的最长递减序列初始化都是1
for i in range(n):
for j in range(i):
if arr[i] dp[i]&＃61;max(dp[i],dp[j]&＃43;1) #找到后&＃xff0c;动态规划&＃xff0c;找到最大的长度
return dp #最后得到的是每个元素的最大递减子序列长度
def generateLST(arr): #获取最大递减子序列的元素
dp&＃61;getdp(arr)
n&＃61;max(dp)
index&＃61;dp.index(n)
lst&＃61;[0]*n #初始化结果列表
n-&＃61;1
lst[n]&＃61;arr[index] #最后一个值容易得到
for i in range(index-1,-1,-1): #从后往前遍历
#当找到比当前元素大并且该元素的最大递减子序列长度比当前元素的最大递减子序列长度小1时
if arr[i]>arr[index] and dp[i]&＃61;&＃61;dp[index]-1:
lst[n]&＃61;arr[i] #该元素就是一个结果&＃xff0c;加入结果列表中
index&＃61;i #更新当前元素
n-&＃61;1
return lst
while(1):
arr&＃61;[int(i) for i in input().split()]
arr.pop(0)
sums&＃61;0
while arr:
sums&＃43;&＃61;1
res&＃61;generateLST(arr) #每次找到最大递减子序列&＃xff0c;这些都可以用一个导弹拦截系统拦截
for i in res: #拦截完就从列表中删除&＃xff0c;一直删除直到列表中没有导弹了&＃xff0c;得到的就是最小的拦截系统数
arr.remove(i)
print(sums)