资源简介

(共28张PPT)
课时40 动态规划
一、动态规划的基本概念
1. 概念：动态规划是一种通过将复杂问题分解为重叠子问题，并利用记忆化存储来优化计算效率的算法策略。
2. 核心思想。
（1）最优子结构：问题的最优解包含其子问题的最优解。
（2）重叠子问题：子问题会被多次重复计算，通过存储结果避免重复求解。
3. 特点：解决子问题采取的决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。
4. 适用场景。
（1）求最大值、最小值或计数问题（如最长递增子序列、最短路径）。
（2）决策问题（如背包问题、零钱兑换）。
1. 定义状态：明确问题的子问题如何表示（通常
用数组或矩阵存储结果）。
2. 状态转移方程：找到子问题之间的关系式。
3. 初始化边界条件：确定最简单子问题的解。
4. 计算顺序：自底向上（迭代）或自顶向下（递归+记忆化）。
二、动态规划的关键步骤
1.斐波那契数列。
（1）问题描述：计算第 n 项斐波那契数（递推公式：F(n)=F(n-1)+F(n-2)）。
（2）Python 实现。
三、动态规划的经典问题与 Python 实现
2.零钱兑换问题。
（1）问题描述：给定不同面额的硬币 coins和总金额 amount，求凑出金额所需的最少硬币数。
（2）状态定义：dp[i]表示凑出金额 i 所需的最少硬币数。
（3）状态转移方程：对于每个金额 i，遍历所有硬 币 coin，若 coin≤i，则 dp[i]=min(dp[i], dp [i-coin]+1)。
（4）Python 实现。
def coin_change(coins,amount):
#float("inf")表示正无穷大
dp=[float("inf")]*(amount+1)
dp[0]=0 #初始化：凑出 0 元需要 0 个硬币
for i in range(1,amount+1):
for coin in coins:
if coin<=i:
dp[i]=min(dp[i],dp[i-coin]+1)
if dp[amount]!=float("inf"):
return dp[amount]
else:
return -1
#示例
coins=[1,2,5]
amount=11
#输出：3（5+5+1）
print(coin_change(coins,amount))
3.最长递增子序列。
（1）问题描述：给定一个数组 nums，求最长递增子序列的长度。
（2）状态定义：dp[i]表示以 nums[i]结尾的最长递增子序列长度。
（3）状态转移方程：对于每个 j（4）Python 实现。
def length_of_lis(nums):
n=len(nums)
dp=[1]*n #初始化
for i in range(n):
for j in range(i):
if nums[j]dp[i]=max(dp[i],dp[j]+1)
return max(dp)
#示例
nums=[10,9,2,5,3,7,101,18]
print(length_of_lis(nums)) #输出：4
4.不同路径问题。
（1）问题描述：在 m×n 网格中，求从左上角到右下角共有多少条路径（只能向右或向下移动）。
（2）状态定义：dp[i][j]表示到达(i,j)的路径数。
（3）状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]（到达(i,j)上方和左方的路径数之和）。
（4）Python 实现。
def unique_paths(m,n):
dp=[[1]*n for _ in range(m)] #初始化
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
#示例
print(unique_paths(3,7)) #输出：28
1. 空间压缩：若状态转移仅依赖前几个状态，可用滚动数组减少空间复杂度。
2. 例如，斐波那契数列只需保存前两项。
def fib_space_optimized(n):
if n<=1:
return n
a,b=0,1
for _ in range(2,n+1):
a,b=b,a+b
return b
四、动态规划的优化技巧
典例 1 工厂在每天的生产中，需要一定数量的零件，同时知道每天生产一个零件的单价。在 n 天的生产中，当天生产的零件可以满足当天的需要，如果有多余的零件，可以放到下一天去使用，但要收取每个零件的保管费，每天收取的保管费可能不相同。
　　已知 n 天的需求量（即 n 天中每天需要的零件个数），需要制定出一个合理的生产计划（即 n 天中每天生产的实际零件个数），使得总费用最少，同时输出最少费用。
　　例如，当n=3时，每天的需求量与费用如表所示。
有多种生产计划，例如下表所示的三种。
显然上述方案中，第二种方案最优。
p[0]=　　　①　　　1
st=0
for i in range(1,n):
if price[i]>price[i-1]+keep[i-1]:
price[i]=price[i-1]+keep[i-1]
p[st]+=need[i]
else:
p[i]=need[i]
　　　②　　　1
t=0 #存储最少费用
for i in range(n):
t+=　　 ③　　　1
return p,t
#主程序
　　　④　　　1
plan,cost=process(need,price,keep)
print(plan,cost)
请回答下列问题：
（1）若把第一个表格中第二天的保管单价改为 5，则总的最少费用为　　　　　　　。
（2）实现上述功能的 Python 程序如下，请在画线处填入合适的代码。
from random import randint
n=100
need=[0]*n #存储每天的需求量
price=[0]*n #存储每天的生产单价
keep=[0]*n #存储每天的保管单价
def make_data():
for i in range(n):
need[i]=randint(1,100)
price[i]=randint(1,100)
keep[i]=randint(1,100)
def process(need,price,keep):
#p 存储每天的生产计划
p=[0]*n
1340
need[0]
st=i
price[i]*p[i]
make_data()
胜券点拨1
明考向 本题主要考查动态规划和贪心算法
审关键 若当天生产单价较高，则在前一天多生产并保管，以减少总费用
考场思维快闪 （1） 若把第一个表格中第二天的保管单价改为5，则第二天的生产单价超过了第一天的生产单价与第一天的保管单价之和（30>20+8）；第三天的生产单价超过了第一天的生产单价与第一、二天的保管单价之和（35>20+8+5），因此当第一天生产50个，第二、三天不生产时，总费用最少，为50×20+30×8+20×5=1340
（2） ①在第一天生产时，由于没有前一天的剩余零件，所以第一天的生产计划应该满足第一天的需求，故填入代码为need[0]。②当price[i]<=price[i-1]+keep[i-1]时，说明当天生产比使用前一天多余的（加上保管费）更划算，所以要更新开始累计生产的索引st，故填入代码为st=i。③将每天的生产量p[i]乘以当天的生产单价price[i]并累加到总费用t中，故填入代码为p[i]*price[i]。④调用make_data函数生成随机数据，故填入代码为make_data()
典例 2 ［2024 温州模拟］将若干件货物装入 n 辆货车，每辆货车载重上限为 m，每件货物的重量不超过 m，所有货物总重量为 n×m。装车过程中，货物不可拆分，每辆货车能满载。
　例如，将 8 件货物装入 4 辆货车，每辆货车的载重上限为 6，每件货物编号及重量如图 a 所示，则各货车装载方案可能有多种，其中一种如图 b 所示，结果为[[1],[2,4],[5,6],[3,7,8]]。
　　编写程序，实现求出各货车装载方案。
请回答下列问题：
（1）将图 a 所示的 8 件货物装入 3 辆货车，每辆货车载重上限为 8，则货车装载的货物编号情况
为[[1,4],　　　　　　　]。
（2）定义如下 Bsort(lst)函数，参数 lst 的每个元素由货物编号和货物重量 2 个数据项组成。函数的功能是根据货物的重量，对 lst 进行降序排序。
def Bsort(lst):
n=len(lst);i=0
while i　　　　　　　1
for j in range(n-1,i,-1):
if lst[j-1][1]lst[j-1],lst[j]=lst[j],lst[j-1]
p=j
i=p
return lst
若 lst 为[[1,6],[2,4],[3,3],[4,2],[5,1], [6,5],[7,2],[8,1]]，请回答下列问题：
①画线处应填入的正确代码是　　　　　　　（单选）。
A.p=0
B.p=n-1
C.i=0
D.i=n-1
②加框处语句的执行次数为　　　　　　　。
[3,6],[2,5,7,8]　或　[2,3,5],[6,7,8]　或　[2,3,8],[5,6,7]（注：数据顺序不做要求）
B
13
（3）实现货物装车功能的部分 Python 程序如下，请在画线处填入合适的代码。
def group(m,n):
global cnt #cnt声明为全局变量
d=[0]*(m+1)
pre=[-1]*(m+1)
for i in range(len(a)): #遍历所有货物
if b[i]: #当前货物未装入货车
'''计算容量为 j 的货车装入当前货物后能达到的最大重量'''
for j in range(m,a[i][1]-1,-1):
if d[j]d[j]=d[j-a[i][1]]+a[i][1]
pre[j]=i
if d[m]==m:
p=m
while pre[p]!=-1:
#取得最后装入货物的索引
j=pre[p]
'''更新剩余容量，取得下一个要装入货物的索引'''
p=p-a[j][1]
#将货物装入当前货车
gnum[cnt%n].append(　　①　　)
q.append([cnt%n,j])
b[j]=False
return True
return False
'''读取每辆货车的载重上限存入 m，所需货车数存入 n；读取所有货物数据，依次存入列表 lst 中。lst[i]包含 2 个数据项，lst[i][0]、lst[i][1]
分别存放货物编号及货物重量，代码略'''
a=Bsort(lst)
b=[True]*len(a) #标记每个货物的状态
cnt=0
gnum,q=[],[]
for i in range(n):
'''gnum[i]存放编号为 i+1 的货车所分配到的货物编号'''
gnum.append([])
while len(q)!=len(a): #还有货物未装入货车
　　　②　　　1
if flag:
cnt+=1
else: #第一辆货车重新装载
tmp=q.pop(0)
gnum[tmp[0]]=[]
　　　③　　　1
#输出每辆货车承载货物的情况，代码略
a[j][0]
flag=group(m,n)
b[tmp[1]]=True
胜券点拨2
明考向 本题主要考查动态规划和回溯算法
审关键 找到一种装载方案，使得每辆货车恰好装满
考场思维快闪 （1） 每辆货车载重上限为8，已知编号为1和4的货物装一辆车，则剩余装载情况可以是[3,6],[2,5,7,8]或[2,3,5],[6,7,8]或[2,3,8],[5,6,7]
（2） ①用变量p跟踪最后一次交换的位置，将下一轮冒泡范围设置为[p,n-1]，这样可以缩小排序范围。每轮排序开始前，将p赋值为n-1，若没有发生交换，则p赋值给i后，将会退出外循环，从而提前结束排序。②加框处语句的执行次数即相邻元素的比较次数，第一轮排序比较7次，第二轮排序比较5次，第三轮排序比较1次，共13次
（3） ①函数group采用动态规划思想，d[i]表示容量为i的货车最多能装入的货物重量，状态转移方程为d[m]=max(d[m],d[m-a[i][1]]+a[i][1])。若d[m]等于m，说明容量为m的货车装满。j为最后装入货物的索引，则对应的货物编号为a[j][0]。②当还有货物未装入货车时，继续寻找调用函数group进行装载，并返回装载情况flag，故填入代码为flag=group(m,n)。③若group(m,n)返回的结果为False，说明没有找到装载方案，则第一辆货车重新装载，即该货车中的货物需要清空（gnum[tmp[0]]=[]），同时相应货物的状态需要恢复为未装车，相应货物的索引为tmp列表的第2个元素，数组b标记每个货物的状态，故填入代码为b[tmp[1]]=True
1.某家庭希望安装节能设备减少水电费，现有n种设备可选。每台设备有安装成本（万元）和每月节省的水电费（元）。预算为4万元，要求选择设备组合使得总节省费用最大。
请回答下列问题：
（1）若可选设备数据如表所示，则总节省费用最大为　　　　　　　元/月。
设备编号 安装成本/万元 每月节省/元
0 1 200
1 2 350
2 3 500
700
（2）实现上述功能的Python程序如下，请在画线处填入合适的代码。
def max_saving(costs,savings,budget):
n=len(costs)
#初始化动态规划表
dp=[[0]*(budget+1) for _ in range(n+1)]
for i in range(1,n+1):
for b in range(budget+1):
if costs[i-1]>b:
'''若当前设备成本超预算，则继承上一行结果'''
dp[i][b]=　　　①　　　1
else:
#选择安装或不安装的较大值
dp[i][b]=max(　　②　　,dp[i-1][b-costs[i-1]]+　 ③ 　)
return dp[n][budget]
costs=[1,2,3]
savings=[200,350,500]
budget=4
maxs=max_saving(costs,savings,budget)
print("最大节省（元/月）：",maxs)
dp[i-1][b]
dp[i-1][b]
savings[i-1]
（1）最优组合为设备0（安装成本1万元，每月节省200元）+设备2（安装成本3万元，每月节省500元），总安装成本为4万元，每月节省700元。　（2）dp[i][b]表示前i个设备在预算为b时的最大节省费用。若当前设备成本超预算，则不安装当前设备，即前i个设备在预算为b时的最大节省费用等于前i-1个设备在预算为b时的最大节省费用（dp[i-1][b]）。不安装时最大节省费用为dp[i-1][b]，安装时最大节省费用等于前i-1个设备在预算为b-costs[i-1]时的最大节省费用（dp[i-1][b-costs[i-1]]）加上当前设备的节省费用savings[i-1]。
2.设有由n个不相同的整数组成的数列，记为：a[1],a[2],…,a[n]，且当i!=j时，a[i]!=a[j]。例如，数列中的数据为3，18，7，14，10，12，23，41，16，24。
若存在i1请回答下列问题：
（1）若数列为32，41，34，42，46，50，37，3，54，18，则数列的最长不下降序列的长度为　　　　　　　。
6
（2）实现上述功能的Python程序段如下，请在画线处填入合适的代码。
a=[3,18,7,14,10,12,23,41,16,24]
n=len(a)
'''
将a扩展成二维数组，每个元素扩展成拥有3个元素的列表：
a[i][0]表示元素值；
a[i][1]表示从位置i开始的最长不下降子序列的长度，初始为1；
a[i][2]表示从位置i开始的最长不下降子序列的下一个位置索引
'''
a=[[x,1,-1] for x in a]
#从后往前查找最长的不下降子序列
for i in range(n-2,-1,-1):
'''记录最长子序列的长度和满足条件的下一个元素索引'''
L,k=0,-1
#查看当前位置之后的所有元素
for j in range(i+1,n):
#若找到一个不下降的元素
if 　　　①　　　:
'''更新L为从位置j开始的最长不下降子序列长度'''
L=a[j][1]
k=j　#记录索引
if L>0:
'''更新a[i][1]，即以i为起点的最长不下降子序列长度'''
a[i][1]=L+1
'''更新a[i][2]，指向下一个元素的索引（生成链表）'''
　　　②　　　1
print("最长不下降序列长度：",　　 ③ 　　)
start=0
#找出最长的不下降子序列的起点
for i in range(1,n):
if a[i][1]>a[start][1]:
start=i
#打印最长不下降子序列
while start!=-1:
print(a[start][0],end=" ")
start=a[start][2]　#移动到下一个节点
a[j][0]>a[i][0] and a[j][1]>L
a[i][2]=k
a[0][1]
（1）最长不下降序列为32，41，42，46，50，54，长度为6。　（2）①若位置j为不下降的元素（a[j][0]>a[i][0]），且从位置j开始的最长不下降子序列长度大于L（a[j][1]>L），则将L更新从位置j开始的最长不下降子序列长度，故填入代码为a[j][0]>a[i][0] and a[j][1]>L。②k为从i开始的最长不下降子序列的下一个位置索引，故填入代码为a[i][2]=k。③最终最长不下降序列长度即从位置0开始的最长不下降子序列长度，故填入代码为a[0][1]。
3.［2025金色阳光联盟］有一个矩形花圃被分成若干方格用于种花，每个方格面积为1，小明想知道该花圃里已经种花的最大矩形区域面积。如图所示的花圃，其已种花的最大矩形区域面积为6。
　　小明编写Python程序解决该问题。他用一个二维列表来表示花圃，则图中的花圃可表示为parterre=[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]，其中“1”表示该位置有种花，“0”表示该位置没有种花。
请回答下列问题：
（1）若parterre的值为[[1,1,1,0,0],[0,1,1,1,1],
[1,1,1,1,1],[1,1,1,1,1]]，则该花圃已经种花
的最大矩形面积是　　　　　　　。
12
（2）实现上述功能的部分Python程序如下，请在画线处填入合适的代码。
def fill(db):
for i in range(n):
count=0
for j in range(m):
if parterre[i][j]==1:
count+=1
　　　①　　　1
else:
count=0
def findMax(x,y):
h,w=1,db[x][y]
maxnum=w*h
for col in range(x+1,n):
if 　　　②　　　:
'''max(a,b)函数用于返回a，b的最大值'''
return max(maxnum,w*h)
elif db[col][y]>=w:
h+=1
else:
h+=1
　　　③　　　1
maxnum=max(maxnum,w*h)
return maxnum
#读取花圃种花数据存入列表parterre
parterre=[[1,1,1,0,0],[0,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]
#获取花圃行、列数
n,m=len(parterre),len(parterre[0])
db=[[0]*m for i in range(n)]
maxnum=0
fill(db)
for i in range(n):
for j in range(m-1,-1,-1):
if db[i][j]!=0:
tem=findMax(i,j)
maxnum=　　　④　　　1
print(maxnum)
db[i][j]=count
db[col][y]==0
w=db[col][y]
max(tem,maxnum)
（1）若parterre的值为[[1,1,1,0,0],[0,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]，则该花圃如图所示，已经种花的最大矩形面积是12。
（2）①函数fill逐行计算二维列表db每个位置左边连续的“1”的数量，存储为db[i][j]，故填入代码为db[i][j]=count。②函数findMax基于预处理后的二维列表db，从每个位置(x,y)向下扩展，计算可能的最大矩形高度和宽度。若当前位置没有种花，说明在矩形区域之外，直接返回maxnum和w*h的最大值，故填入代码为db[col][y]==0。③若当前位置有种花，则矩形高度增加1，若当前位置左边连续“1”的数量小于上一位置左边连续“1”的数量，则矩形宽度更新为当前位置左边连续“1”的数量，故填入代码为w=db[col][y]。④计算以位置(i,j)为矩形右上角的最大矩形，不断更新矩形面积的最大值，故填入代码为max(tem,maxnum)。
4.［2024 金兰教育联考］马拦过河卒。小明同学最近迷上了下象棋，在一次与爸爸的对弈中，棋盘上 A点有一个过河卒，需要走到目标 B 点。卒行走的规则：每次只能向下或向右移动一步。在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为该马的控制点。如图 a 所示，马位于 C 点，而 P1~P8 是马一步可到的点，这些点被称为卒的禁区。小明同学编写了一个程序，计算马在 C 点的情况下，卒从 A 点到 B 点的方案有多少种。
　　例如，图 a 中起始点 A 的坐标为(0,0)，目的地 B的坐标为(5,6)，马的坐标为(3,3)，从 A 点到 B 点的路径数量为 3，图 b 和图 c 是其中两条可能的路径。
def control(row,col,crow,ccol):
'''dir 存储各控制点相对于马的坐标，如图 a中点 P1 和 P2 分别用[2,1]和[1,2]表示'''
dir=[[0,0],[2,1],[1,2],[-1,2],[-2,1], [-2,-1],[-1,-2],[1,-2],[2,-1]]
for i in range(9):
if 　　　　　　　:
return True
return False
请回答下列问题：
（1）若将图 a 中目的地 B 的坐标改为(6,6)，起始点 A和马的坐标均不变，则从 A 点到 B 点的路径数为　　　　　　　。
（2）小明首先设计了一个自定义函数 control(row,col,crow,ccol)，用于判断点(row,col)是否为马的控制点，若是则返回 True，否则返回 False。已知马所在坐标为(crow,ccol)，请在划线处填入合适的代码。
6
dir[i][0]+crow==row and dir[i][1]+ccol==col
arr[0][i]=1
#遍历第一列元素
for i in range(1,n+1):
if control(i,0,x,y):
break
　　　②　　　1
for i in range(1,n+1):
for j in range(1,m+1):
if not control(i,j,x,y):
arr[i][j]=　　　③　　i
print(f"从(0,0)到({n},{m})的可行路径共有{arr[n][m]}条")
（3）假设棋盘的大小是 30×30 的网格，卒的起始点 A 坐标为(0,0)，设置 arr[0][0]的值为 1，表示从起始点到(0,0)的路径数量为 1。程序从键盘输入目标点 B 的位置(n,m)和马的位置(x,y)，通过遍历网格，统计卒在避开马的控制点的情况下，按规则从 A 点到 B 点的可行路径数量。请在划线处填入合适的代码。
n,m,x,y=map(int,input("请输入目的地和马的坐标（用空格隔开）：").split())
arr=[[0]*30 for i in range(30)]
arr[0][0]=1
#遍历第一行元素
for i in range(1,m+1):
if control(0,i,x,y):
　　　①　　　1
break
arr[i][0]=1
arr[i-1][j]+arr[i][j-1]
（1）从(0,0)到(5,6)有 3 条可行路径，从(0,0)到(6,5)有 3 条可行路径，因此从(0,0)到(6,6)有 6 条可行路径。 （2）各控制点相对于马的坐标为(dir[i][0],dir[i] [1])，马的坐标为(crow,ccol)，则各控制点的坐标为(dir[i][0]+crow,dir[i][1]+ ccol)，要判断点(row,col)是否为马的控制点，故填入代码为 dir[i][0]+crow==row and dir[i][1]+ccol==col。 （3）①若 control(0,i,x,y)的值为 False，说明(0,i)不是马的控制点，从起始点到(0,i)的路径为 1（只能向右走），若 control(0,i,x,y)的值为 True，说明(0,i)是马的控制点，无法从起始点到(0,i)，也无法从起始点到(0,i)右方的点，因此提前退出循环，故填入代码为 break。②若 control(i,0,x,y)的值为 False，说明(i,0)不是马的控制点，从起始点到(i,0)的路径为 1（只能向下走），若 control(i,0,x,y)的值为 True，说明(i,0)是马的控制点，无法从起始点到(i,0)，也无法从起始点到(i,0)下方的点，因此提前退出循环，故填入代码为 arr[i] [0]=1。③对于非边界点(i,j)，若(i,j)不是马的控制点，则从起始点到(i,j)的路径数等于起始点到(i,j)上侧点和(i,j)左侧点的路径数之和，故填入代码为 arr[i-1][j]+arr[i][j-1]。

展开更多......

收起↑