动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
以上定义来源于维基百科，老规矩，直接来做板子题。
以下共四道板子题：
1.数字金字塔
2.最长上升子序列
3.最长公共子序列
4.最简单的01背包
板子题1-金字塔路径： 题目描述观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 7→3→8→7→5 的路径产生了最大
输入格式第一个行一个正整数 r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式单独的一行,包含那个可能得到的最大的和。
输入5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30
【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。
思路解析
这道题要求的是从金字塔顶端到底端的最长路径。
主要思路就是动态规划。
上文提到，动态规划的核心思路是把一个大问题分解成若干个简单的、可重复的子问题。
以这道题为例，所谓的大问题是“获取最短路径”，而小问题则是“选择数字，并使得本次选择能使总数字最小”。
（本题并不适用于贪心，虽然贪心也要把大问题分解为若干个小问题，但是贪心的核心条件是，“每一步不能对后一步有影响”，这也就是“贪心选择性质”。）
7 #如果按照贪心，我们从7开始，就是7-8-1-7-5，比7-3-8-7-5要小。
3 8
8 1 0
2 7 4 4
4 5 2 6 5
我们先从7试试。
如果从7开始，第一步可以选择（3，8）。
但是，下一步是从3开始还是从8开始呢？答案是不一定，在这个 *** 作的时候还不能确定。
刚刚已经分析过了，这个题不具备贪心选择性质，因此我们需要把选择的结果作为一个状态保存下来。
肯定不能保存在7这个位置上，一个位置咋可能保存俩信息，所以保存在3，8上。
那继续分析，比如用倒数第二层的7来看。
这个位置的下一层（也就是倒数第一层）应该选择谁？显然是5。
所以，从最后一层起，每层都选取它下两个数中大的那一个。（因为无论选择哪一个，都不影响后续，后续都是从这个数开始）
如果我们最后一层开始，那么到7这个位置就好选了：选择（3，8）这两个位置中，从其自身开始的路径最大的位置。
接下来说一说代码。
我们用dp[i][j]来标记数组中第i位，并且从倒数第二排开始遍历，使得每一位数值等于其下端两位数字的最大值。
也就是说，dp[i][j] += max( dp[i+1][j], dp[i+1][j+1])
#5 #第一个数字为行数
#7 #第一行，1个元素
#3 8 #第二行，2个元素
#8 1 0 #第三行，3个元素
#2 7 4 4 #第四行，4个元素
#4 5 2 6 5 #第五行，5个元素
#输入格式，第一个部分为行数
n = int(input())
#而后输入n行元素，我们用列表来存储
ls = []
for i in range(n):
ls.append( list( map(int, input().split() ) ) )
#好了，到这里，数据已经以
#ls = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]的形式存储了。
#
#
#代码部分
#
#
#然后考虑输出，由于我们的思路是从下到上，所以最后ls[0][0]的位置就应该是答案
print(ls[0][0])
for i in range(n - 2, -1, -1):
#外层循环，倒数第二层到0层
for j in range(i+1):
#内层循环，第一个元素到本层最后一个
ls[i][j] += max(ls[i+1][j], ls[i+1][j+1])#状态转移方程
n = int(input())
ls = []
for i in range(n):
ls.append( list( map(int, input().split() ) ) )
for i in range(n - 2, -1, -1):
for j in range(i+1):
ls[i][j] += max(ls[i+1][j], ls[i+1][j+1])
print(ls[0][0])
【洛谷P1216】https://www.luogu.com.cn/problem/P1216
板子题2-最长上升子序列： 题目描述某国为了防御敌国的导d袭击，发展出一种导d拦截系统。但是这种导d拦截系统有一个缺陷：虽然它的第一发炮d能够到达任意的高度，但是以后每一发炮d都不能高于前一发的高度。某天，雷达捕捉到敌国的导d来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导d。
输入导d依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导d，如果要拦截所有导d最少要配备多少套这种导d拦截系统。
输入格式1行，若干个整数（个数≤100000）
NOIP 原题数据规模不超过 2000。
输出格式2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导d，第二个数字表示如果要拦截所有导d最少要配备多少套这种导d拦截系统。
输入389 207 155 300 299 170 158 65
6
2
为了让大家更好地测试n方算法，本题开启spj，n方100分，nlogn200分
每点两问，按问给分
思路解析
这道题的板子题其实是最长上升序列，但是这个，嘶，只找到了这种描述的，没有找到纯板子的那种。
那就还是先读一下题意。
虽然它的第一发炮d能够到达任意的高度，但是以后每一发炮d都不能高于前一发的高度。（递减数列嘛）
某天，雷达捕捉到敌国的导d来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导d。
1.计算这套系统最多能拦截多少导d。 （也就是最长的不上升序列）
2.如果要拦截所有导d最少要配备多少套这种导d拦截系统。（也就是最长的上升序列）
其实这个题的最优时间复杂度是O(NlogN)，但是我们现在只介绍N^2的算法。
还是之前的思路，我们要解决的问题是，从一个序列中找到最长的上升序列。
对于1243这个序列而言，它的最长上升子序列长度和124这个序列是一样的。
因此，我们令dp[i]表示以第i位结尾的最长上升子序列长度。
那么，在123到1243的这个时候发生了什么呢？
我们首先判断了1、2、4的大小，把比3小的拿了出来：[1,2]
然后，在1，2中选择其更长的，接在3前面。所以，最后的答案是123。
综上所述：
DP维度：一维
数组初始化：初始化为1（每个位置各是一个长度）
DP数组含义：dp[i]代表以ls[i]结尾的最长上升序列长度
状态转移方程：dp[i] = max( dp[j] ) (j ∈ {0,1,2…i}, ls[j] < dp[j] )
输入输出部分#输入的是一行数，那就不多说了。
ls = list( map( int, input().split() ) )
#
#
#输出的就是数列里最大的值
print(max(dp))
print(max(dp_2))
dp = [1] * len(ls)#因为我们这个题求了两个东西，所以声明两个数组，初始化为1
dp_2 = [1] * len(ls)
for i in range(len(ls)):#循环
maxn = 0
maxn_2 = 0#用一个变量标记本次循环中，前面最大的值
for j in range(i):
if ls[j] >= ls[i] and dp[j] > maxn:#如果不递增
maxn = dp[j]
if ls[j] < ls[i] and dp_2[j] > maxn_2:#如果递增
maxn_2 = dp_2[j]
dp[i] += maxn#更新两个dp数组
dp_2[i] += maxn_2
ls = list( map( int, input().split() ) )
dp = [1] * len(ls)
dp_2 = [1] * len(ls)
for i in range(len(ls)):
maxn = 0
maxn_2 = 0
for j in range(i):
if ls[j] >= ls[i] and dp[j] > maxn:
maxn = dp[j]
if ls[j] < ls[i] and dp_2[j] > maxn_2:
maxn_2 = dp_2[j]
dp[i] += maxn
dp_2[i] += maxn_2
print(max(dp))
print(max(dp_2))
【洛谷P1020】https://www.luogu.com.cn/problem/P1020
但是，只能拿到70分，时间复杂度更优的算法以后会写~
板子题3-最长公共子序列： 题目描述给出 1,2,…,n 的两个排列，P1和P2，求它们的最长公共子序列。
输入格式第一行是一个数 n。
接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。
输出格式一个数，即最长公共子序列的长度。
输入5
3 2 1 4 5
1 2 3 4 5
3
- 对于 50% 的数据， n≤10^3；
- 对于 100%的数据， n≤10^5。
思路解析
这个找到了板子题！
我们要解决的问题是，两个序列的最长公共序列。
比如
序列一为 1, 2, 7, 6, 3
序列二为 1, 7, 6, 3, 2
此时，一维的dp肯定是不够的，因为我们有两个序列，不能用一个序列装下。
所以，我们用dp[i][j]来表示ls1[:i]和ls2[j:]的公共子序列。
我们随便找个中间态来模拟一下。
假设我们现在要求解的状态是len(ls1) = 4, len(ls2) = 3
那么，在上一个状态转移到下一个状态的过程中，我们需要判断新增的元素能不能添加进已有最长公共序列的末尾。
它的上一个状态会是什么呢？答案是不一定。
len(ls1) = 4, len(ls2) = 3
它可以由len(ls1) = 3, len(ls2) = 3和len(ls1) = 4, len(ls2) = 2继承而来（这两个状态都可以添加一个元素以变成当前状态）
而这两个在dp数组中存储的数值可能是不一样的，要判断一下。
因此，我们要比较ls1[4]和ls2[3]是否相等，如果相等，说明此位置可以加入新公共序列
如果不相等，就只能继承能达到此状态的最有状态。
数组初始化：没啥用，继承
DP数组含义：dp[i][j]来表示ls1[:i]和ls2[j:]的公共子序列长度。
状态转移方程：dp[i][j] = {继承 max(dp[i-1][j],d[i][j-1]) ， 如果相等再加一}
#先输入一个n
n = int(input())#但是这玩意没啥用，毕竟我们用的是Python，顶多不用求len()了
ls1 = list( map( int, input().split() ) )
ls2 = list( map( int, input().split() ) )
#
#核心代码
#
#输出的答案应该是dp[n][n]的数值
print(dp[n][n])
dp = [[ [0,""] for j in range(n+5)] for i in range(n+5)]#顺便保存了一下序列
for i in range(1, n+1):
for j in range(1, n+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0])#状态转移方程
dp[i][j][1] = dp[i-1][j][1] if dp[i-1][j][0] > dp[i][j-1][0] else dp[i][j-1][1]
if ls1[i-1] == ls2[j-1]:
dp[i][j][0] += 1#更新
dp[i][j][1] += ls1[i-1]
n = int(input())
ls1 = list( input().split() )
ls2 = list( input().split() )
dp = [[ [0,""] for j in range(n+5)] for i in range(n+5)]
for i in range(1, n+1):
for j in range(1, n+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0])
dp[i][j][1] = dp[i-1][j][1] if dp[i-1][j][0] > dp[i][j-1][0] else dp[i][j-1][1]
if ls1[i-1] == ls2[j-1]:
dp[i][j][0] += 1
dp[i][j][1] += ls1[i-1]
#输出的答案应该是dp[n][n]的数值
print(dp[n][n][0])
print(dp[n][n][1])
【洛谷P1439】https://www.luogu.com.cn/problem/P1439
但是，看数据范围，我们的算法只能拿到50分，时间复杂度更优的算法以后会写~
板子题2/3-思路调优： 时间复杂度分析首先，目前最长上升子序列的时间复杂度为n2，最长公共子序列也是n2
但是他们都有各自的nlogn算法：二分+动态规划
这部分内容我会陆续在我的个人博客更新~
转换思路思考一下，对[4,1,5,2,3]求最长递增序列，是不是就是对这个队列求他和[1,2,3,4,5]的最长公共子序列？
所以，也可以自定义”大小比较“，将公共子序列转化为上升子序列问题。
板子题4-最简单的01背包： 题目描述辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。
第 2 到第 (m+1) 行，每行两个整数，第 (i + 1)行的整数 a_i, b_i分别表示采摘第 i 种草药的时间和该草药的价值。
输出格式输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
输入70 3
71 100
69 1
1 2
140
- 对于 30% 的数据，保证m <10^3。
- 对于 100%的数据，保证 1≤m≤10^4, 1≤t≤10^7，且 1≤m×t≤10^7, 1≤ ai, bi ≤10^4
一个背包问题。
01背包问题的常见模板是什么样子的呢？
1.给定若干个物品，每个物品都有一些属性，比如价值和重量
2.每个物品都有两种可能，选还是不选
3.我们的背包可能只能装50重量，选择价值尽可能多的物品
这个问题还是可以用动态规划来解决，因为每一个物品都可以”选“或者”不选“，这就是重复的子问题。
我们现在要理解一个概念：
假设，一共有五个物品：
A，价值3，重量1
B，价值1，重量2
C，价值8，重量3
D，价值2，重量1
E，价值4，重量2
你一共可以选择五件（一共就五件嘛），总重量不能超过7
#下标从一开始
首先我们先设个状态，比如dp[i]][j]代表前i件物品、总重量不超过j的最大价值。（所以答案就是dp[5][7]）
但是，他肯定不能只存储这一个信息，因为还有个信息是重量。那我们就可以令dp[i] = [value, weight]，来计算和存储。
我们假设，只有前四件物品可以拿，现在要准备拿第五件，这两个状态转移过程中发生了什么呢？
dp[5]，唯一要决定的事情是第五件物品拿还是不拿。
如果第五件物品拿，那么dp[5][7] = dp[4][7-2(E的重量)]+value[5]
如果第五件物品不拿，那么dp[5][7] = dp[4][7]
所以，我们就要比较一下这俩，取一个max值就可以了。
所以我们很轻易的得到了状态转移方程：
数组初始化：没啥用
DP数组含义：dp[i][j]来表示ls1[:i]和ls2[j:]的公共子序列长度。
状态转移方程：dp[i][j] = max(dp[i-1][j],d[i-1][j-weight[i]] + value[i])
#输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。
t, m = map(int, input().split())
#第 2 到第 (m+1) 行，每行两个整数，第 (i + 1)行的整数 a_i, b_i分别表示采摘第 i 种草药的时间和该草药的价值。
value = [0]
time = [0]
for i in range(m):
t_i, v_i = map(int, input().split())
value.append(v_i)
time.append(t_i)
#
# 核心代码
#
#输出就是dp[m][t]
print(dp[m][t])
dp = [[0] * (m + t)]* (m + t)
for i in range(n):
for j in range(n):
dp[i][j] = max(dp[i-1][j], d[i-1][j-time[i]] + value[i])for i in range(1,m+1):#判断第i件物品
for j in range(1,t+1):#在time剩余j的情况下
if j - time[i] >= 0:#如果时间够
dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i]] + value[i])
else:
dp[i][j] = dp[i-1][j]
t, m = map(int, input().split())
value = [0]
time = [0]
for i in range(m):
t_i, v_i = map(int, input().split())
value.append(v_i)
time.append(t_i)
dp = [[ 0 for j in range(t+2)] for i in range(m+2)]
for i in range(1,m+1):
for j in range(1,t+1):
if j - time[i] >= 0:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i]] + value[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[m][t])
【洛谷P048】https://www.luogu.com.cn/problem/P1048
更多算法，详见个人博客，[http://fengjx.cn]
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）