下载文档原格式
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
动态规划例题动态规划是一种以最优化原理为基础的问题求解方法，通过拆分问题为若干阶段，每个阶段求解一个子问题，再逐步推导出整个问题的最优解。
例如，有一个背包能够承受一定的重量，现有一些物品，每个物品都有自己的重量和价值。
我们希望将物品放入背包中，使得背包的总价值最大。
这个问题可以用动态规划来解决。
首先，我们定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，容量为j的背包中所能放入的物品的最大价值。
那么，对于每一个物品，可以选择放入背包或者不放入背包。
如果选择放入背包，最大价值为dp[i-1][j-w[i]] + v[i]，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
如果选择不放入背包，最大价值为dp[i-1][j]。
因此，dp[i][j]的状态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j])。
基于这个状态转移方程，可以逐步求解从第1个物品到第n个物品的最大价值。
最终，dp[n][W]即为问题的最优解，其中W 表示背包的容量。
举个简单的例子，假设背包的容量为10，有3个物品，它们的重量分别为3、4、5，价值分别为4、5、6。
此时，可以得到如下的dp矩阵：0 0 0 0 0 0 0 0 0 0 00 0 0 4 4 4 4 4 4 4 40 0 0 4 5 5 9 9 9 9 90 0 0 4 5 5 9 10 10 14 14我们可以看到，dp[3][10]的最大价值为14，表示在前3个物品中，容量为10的背包中所能放入的物品的最大价值为14。
通过动态规划，我们可以有效地求解背包问题，得到物品放入背包的最优解。
这个例子只是动态规划的一个简单应用，实际上，动态规划可以解决各种复杂的问题，如最长公共子序列、最大子数组和、最大字段和等。
因此，学习动态规划是非常有意义的。
动态规划专题分类视图数轴动规题： (1)较复杂的数轴动规 (4)线性动规 (7)区域动规： (14)未知的动规： (20)数轴动规题：题1.2001年普及组第4题--装箱问题【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积（正整数）。
要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
【输入格式】输入文件box.in有若干行。
第一行：一个整数，表示箱子容量V；第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。
【输出格式】输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。
【输入样例】2468312797【输出样例】题2.1996年提高组第4题--砝码秤重__数据加强版【问题描述】设有n种砝码,第k种砝码有C k个,每个重量均为W k,求：用这些砝码能秤出的不同重量的个数，但不包括一个砝码也不用的情况。
【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量.【输出格式】输出文件weight.out中只有一行数据:Total=N。
表示用这些砝码能秤出的不同重量数。
【输入样例】22 22 3【输出样例】Total=8【样例说明】重量2,3,4,5,6,7,8,10都能秤得【数据限制】对于100%的数据,砝码的种类n满足:1≤n≤100;对于30%的数据,砝码的总数量C满足:1≤C≤20;对于100%的数据,砝码的总数量C满足:1≤C≤100;对于所有的数据,砝码的总重量W满足:1≤W≤400000;题3.石子归并-szgb.pas【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。
【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。
动态规划应用案例动态规划是一种解决复杂问题的优化算法。
它通过将问题拆分成多个子问题，并记录每个子问题的解，以避免重复计算，从而提高算法的效率。
在实际应用中，动态规划被广泛用于解决各种问题，包括最优化问题、路径搜索问题、序列问题等。
本文将介绍几个动态规划的应用案例，以展示其在实际问题中的强大能力。
案例一：背包问题背包问题是动态规划中经典的一个例子。
假设有一个背包，容量为V，现有n个物品，每个物品的重量为wi，价值为vi。
要求在不超过背包容量的前提下，选取一些物品放入背包，使得背包中的物品总价值最大。
这个问题可以用动态规划来解决。
首先定义一个二维数组dp，其中dp[i][j]表示在前i个物品中选择一些物品，使得它们的总重量不超过j时的最大总价值。
然后，可以得到如下的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)最后，根据状态转移方程，可以循环计算出dp[n][V]的值，即背包中物品总价值的最大值，从而解决了背包问题。
案例二：最长递增子序列最长递增子序列是指在一个序列中，选取一些数字，使得这些数字按照顺序排列，且长度最长。
动态规划也可以应用于解决最长递增子序列问题。
假设有一个序列nums，长度为n。
定义一个一维数组dp，其中dp[i]表示以nums[i]为结尾的最长递增子序列的长度。
然后，可以得到如下的状态转移方程：dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]最后，循环计算出dp数组中的最大值，即为最长递增子序列的长度。
案例三：最大子数组和最大子数组和问题是指在一个数组中，选取一段连续的子数组，使得子数组的和最大。
动态规划也可以用于解决最大子数组和问题。
假设有一个数组nums，长度为n。
定义一个一维数组dp，其中dp[i]表示以nums[i]为结尾的连续子数组的最大和。
然后，可以得到如下的状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])最后，循环计算出dp数组中的最大值，即为最大子数组的和。
动态规划问题常见解法动态规划（Dynamic Programming）是一种常用的算法思想，用于解决一类具有重叠子问题性质和最优子结构性质的问题。
动态规划通常通过将问题划分为若干个子问题，并分别求解子问题的最优解，从而得到原问题的最优解。
以下是动态规划问题常见的解法：1. 斐波那契数列斐波那契数列是动态规划问题中的经典案例。
它的递推关系式为 F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1。
可以使用动态规划的思想来解决斐波那契数列问题，通过保存已经计算过的子问题的结果，避免重复计算。
2. 背包问题背包问题是一个经典的优化问题，可以使用动态规划的方法进行求解。
背包问题包括 0/1 背包问题和完全背包问题。
0/1 背包问题中每个物品要么被选中放入背包，要么不选。
完全背包问题中每个物品可以被选中多次放入背包。
通过定义状态转移方程和使用动态规划的思想，可以高效地求解背包问题。
3. 最长递增子序列最长递增子序列是一个常见的子序列问题，可以使用动态规划的方法进行求解。
最长递增子序列指的是在一个序列中，找到一个最长的子序列，使得子序列中的元素按照顺序递增。
通过定义状态转移方程和使用动态规划的思想，可以有效地求解最长递增子序列问题。
4. 最长公共子序列最长公共子序列是一个经典的字符串问题，可以使用动态规划的方法进行求解。
给定两个字符串，找到它们之间最长的公共子序列。
通过定义状态转移方程和使用动态规划的思想，可以高效地求解最长公共子序列问题。
5. 矩阵链乘法矩阵链乘法是一个求解最优括号化问题的经典案例，可以使用动态规划的方法进行求解。
给定多个矩阵的大小，需要找到一个最优的计算顺序，使得计算乘积的次数最少。
通过定义状态转移方程和使用动态规划的思想，可以高效地求解矩阵链乘法问题。
以上是动态规划问题的常见解法，通过使用动态规划的思想和方法，可以解决这些问题，并求得最优解。
动态规划专题( 四 )线性动态规划所谓线性动态规划, 意思是问题的状态可以描绘在一条直线上, 通过对直线上的状态选择, 来逐步推导出问题的最优解。
下面我们先来看一个简单问题。
[ 侧门台帽队形N 位同学站成一排, 音乐老师要请其中的(N-K) 位同学出列, 使得剩下的K 位同学排成合唱队形。
合唱队形是指这样的一种队形: 设K 位同学从左到右依次编号为1,2, …,K, 他们的身高分别为ThTZ' …, 飞, 则他们的身高满足T!<Tz<" ·Ti' Ti>Ti+l> …>Td1 运i:O:::;K) 。
你的任务是, 已知有N 位同学的身高, 计算最少需要几位同学出列, 可以使得剩下的同学排成合唱队形?[ 输入文件]输入文件chorus.in 的第一行是一个整数N(2:O:::;N:O:::;l ∞), 表示同学的总数。
第→行有n 个整数, 用空格分隔, 第i 个整数Ti(130:O:::;Ti:O:::; 230) 是第i 位同学的身高( 厘米) 。
[ 辅出文件]输出文件chorus. out 包括一行, 这一行只包含一个整数, 就是最少需要几位同学出列。
[ 样倒输入]8186 186 150200 160 130 197220[ 样倒骗出]4【撞撞规模]对于500 毛的数据, 保证有n:O:::;20; 对于全部的数据, 保证有n:O:::;l ∞。
[ 分析]本题描述为: 在一条直线上的n 个人, 要找出某个最长的队列, 其中队列中最高的人, 他左边的人的高度呈升序排列, 他右边的人的高度呈降序排列。
例如样例中可以选以下这样的队列, 答案都为4:150 160 197220 或150200 160 130 ,1862 ∞160130一种比较直观的想法: 在队列中枚举那个最高的人, 然后从该人开始对左边求最长的上升序列, 假设长度1en1, 对右边求最长的下降序列, 假设长度为len2, 那么答案就len=len1 +len2-1 0那么问题就转化为, 对于一个直线上的若干个数, 如何求最长上升( 或下降) 序列的长度。
下面我们以求最长上升序列为例进行说明, 求最长下降序列类似。
设f(i) 表示前i 个数的最长上升序列的长度。
f(i) 的数值能否递增, 取决于第i 个数与前面数值的大小关系, 对于j<i, 如果a[j]<a[i], 则表示第j 个数到第i 个数是递增的, 符合题意,f 值也可以递增。
因此有:f(i)=m 叫fO)}+ 1 ,a[j]<a[i] 公式1jd,2,"',i-!初始值:f( 0=1答案: max{f(i)},i=1,2, …,n因为要枚举i 和J, 所以时间复杂度为:0(n 币。
回到原问题, 还需要枚举最高的人, 因此总时间复杂度为O( 的。
进一步分析: 其实在做枚举时, 左边求最长上升序列, 右边求最长下降序列, 也可以这样说, 从左至右求一遍最长上升, 再从右至左也求一次最长上升, 求完后, 任取某个元素作为最高者, 都会符合合唱队形。
因此我们只要对所有这样的合唱队形找一个最大数值即可。
以样倒说明, 假设从左至右求最长上升的序列为t 从右至左求最长上升的序列为g, 显然答案为max{f(i)+g(i)-l },i=l, 2, …,n 。
因此只要分别从左右求出两个最长上升序列后, 最后再去枚举每个转折点即可。
时间复杂度为: O( 的。
样例如下:186 186 150 2 ∞160 130 197 220 _ 1 1 122 1 3 4 g: 3 3 2 3 2 1 1 1f+g: 4 4 3 5 4 2 4 5进一步观察公式1, 求削时, 其实是找所有符合条件均) 的最大值, 假设存在k,j<i,a[k] <a[i], a[j] 芥<a[i 且i] 口,co 位刷()=fi 王吗G ω)显然如果a[ 悻剧k 问]< 也 a 甜[j], 我们需要保存a[ 悻剧k 剖], 舍去a[j], 因为它们两个f 值一样, 那么后面的数x 如何能与a[j]% 成升序? 显然与唯] 也能, 反之则不然。
口长沙市雅礼中学朱全民这样, 我们只要维护一个f 值和a 值都上升的队列, 运用折半查找方法找到能进行决策转移的最大f 值, 然后进行转移即可。
以样例为例说明:原始序列: 186 186 150 2 ∞160 130 197220队列: 186(f=0, 186(_=1,f 和a 的数值都相同, 舍去)队列: 186(_=1),150(_=1), 此时150<186,仨1, 因此用150 更新186队列: 150(_=1 ),2 ∞(f=2)队列: 150 (_=1 ),2 ∞(f=2),1 ω(f=2), 同样160<2 ∞,f=2, 因此用160 更新2 ∞队列: 150(_=1 ),16O(f= 匀,130 (f=l ), 同样130<150,f=1, 因此用130 更新150队列: 130(_=1 ),16O(f=2),197(_=3)队列: 130(_=0, 16O(f=2), 197(_=3),220(f=4)由此可见, 我们队列始终都是一个 a 和 f的上升序列, 由于队列有序, 因此可以采用折半查找方法找到更新点, 这样查找决策的时间变为logzn, 因此求最长上升序列的时间复杂度为O(n*logzn) 。
【倒2 】过湾在河上有一座独木桥, 一只青蛙想沿着独木桥从河的一侧跳到另一侧。
在桥上有一些石子, 青蛙很讨厌踩在这些石子上。
由于桥的长度和青蛙一次跳过的距离都是正整数, 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1, …,L( 其中L 是桥的长度) 。
坐标为0 的点表示桥的起点, 坐标为L 的点表示桥的终点。
青蛙从桥的起点开始, 不停地向终点方向跳跃。
一次跳跃的距离是S 到T 之间的任意正整数( 包括S,T) 。
当青蛙跳到或跳过坐标为L 的点时, 就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L, 青蛙跳跃的距离范围S 几桥上石子的位置。
你的任务是确定青蛙要想过河, 最少需要踩到的石子数。
【辅λ立件]输入文件river. in 的第一行有一个正整数L(1_ 三L:O:::;109), 表示独木桥的长度。
第二行有三个正整数S,T,M, 分别表示青蛙一次跳跃的最小距离、最大距离及桥上石子的个数, 其投稿信箱:Benami@ _中I:::;S 运T:::;lO,I:::;M:::;loo 。
第三行有M 个不同的正整数, 分别表示这M 个石子在数轴上的位置( 数据保证桥的起点和终点处没有石子) 。
所有相邻的整数之间用一个空格隔开。
[ 输出文件]输出文件由er.out 只包括一个整数, 表示青蛙过河最少需要踩到的石子数。
[ 样倒辅λ]1023523567[ 样倒辅出]2[ 撞撞规模]对于30l) 毛的数据,L 运10 ∞0; 对于全部的数据,L_ 三109 。
[ 纷析]这个桥可以抽象成为一个数轴, 也就是一条线, 青蛙在线上跳跃方法为决策数, 由于不能往回跳, 符合动态规划的无后效性, 因此可以用线性类动态规划方法解决该题。
同最长上升序列类似, 设f(i) 表示青蛙跳到第i 个点需要踩到的最少石子数, 则有: f(i-k)}+ l,a[i] 险为石子f(i)=min K=S"'T公式 2f(i-k),d[i] 处没有石子初始值:f(O)=O答案:min{fi 剧, 他+1), …,f(L+T-l)} 因为要枚举i 和k, 所以时间复杂度为:O(σ'-S+l)*L) 。
由于本题的L 高达109, 因此当L 比较大时, 肯定不能在规定的时限内出解。
考虑这样一个现实问题: 当长度为k 的一段没有石子的独木桥, 判断是否存在一种跳法从一端正好跳到另一端。
若S<T, 事实上对于某个可跳步长区间[S, T], 必然存在一个MaxK 使得任何k:;;.M 缸K, 都可以从一端正好跳到另一端。
由于题设中青蛙的步长都在10 步以内, 经过简单推导可以验证, 取M 缸K=100 就能满足所有区间。
于是我们可以分两种情况讨论: 1.S=T B 才:这时候由于每一步只能按固定步长跳, 所以若第i 个位置上有石子并且i mod S=O, 那么这个石子就一定要被踩到。
这是我们只需要统计石子的位置中哪些是S 的倍数即可。
复杂度。
(M)2.S<T 时:首先我们作如下处理: 若存在某两个相邻石子之间的空白区域长度大于M 缸K+2*T, 我们就将这段区域缩短成长度为MaxK+2 叮。
可以证明处理之后的最优值和原先的最优值-投稿信箱:Benami@1 日 .∞m相同。
＼/…...0000a …,00900.. …·文件的第一行是两个正整数N 和M(I:::; M_ 三N:::;IOO), 分别表示积木总数和要求摞成的柱子数。
这两个数之间用一个空格符隔开。
接下来的N 行是编号从 1 到N 个积木的尺寸, 每行有三个1 至5 ∞之间的整数, 分别表示该积木三条边的长度。
同一行相邻两个数之间用一个空格符隔开。
[ 辅出搬握]文件只有一行, 是一个整数, 表示所求得的游戏方案中M 根柱子的高度之和。
[ 分析]条件规定:(1) 积水从前往后编了号;(2)后面的柱子中的积木编号必须比前面的柱子中的积木编号大: (3) 对于同一根柱子, 上面的积木的编号必须大于下面的积木的编号。
因此可以将上述条件理解为: 有N 个积木摆放在一条线上, 每次都只能从前往后拿积木, 拿的积木也只能摆放在后面的柱子上的最上层。
可见这道题的无后效性很明显, 对于第i 块积木转移, 它的决策仅仅取决于前i-I 块积木的摆放, 而与后面的积木无关。
这样我们很自然地想到采用线性类的动态规划。
对于取到的当前积木, 有以下几种情况: 1 要么不用;2. 要么摆放在当前柱的最上层;3. 要么作为下一根柱子的第一个积才旦。
而对每块积木, 摆放的方式有3 种, 假设积木的长和宽高分别为:a 、 b 、c; 第 1 种:a,b 面朝上, 高为 c 第2 种:b,c 面朝上, 高为 a 第 3 种:a,c 面朝上, 高为b假设用block [i,k] 表示第i 块积木的第k 条边的长度;k=0,1,2; 这里可以实现对每个积木的三条边进行排序, 使得block[i,O] :::; block[i,1] 运block[i,2] , 便于比较。
我们需要先将任意两块积木是否能叠放进行初始化。
用can(i 木,j,p) 记录第i 块积木的第k 面是否能与第j 块积木的第p 面叠放。
