动态规划例题讲解

概率dp例题？
答：以下是一个概率动态规划的例子：
假设有一个长度为n的楼梯，每次可以跨1级或2级。

求总共有多少种不同的方法可以爬到楼梯顶部。

解法：设f(n)表示爬到第n级楼梯的方法总数。

对于第n级，有两种方式到达：从第n-1级跨一步，或者从第n-2级跨两步。

所以，我们有f(n)=f(n-1)+f(n-2)。

这就是一个典型的动态规划问题，可以通过迭代求解。

初始条件是：f(1)=1, f(2)=2。

用这些初始条件和递推关系，我们可以求解f(n)对于任意n的值。

如果我们要找的是爬到第10级楼梯的方法数，可以按照以下步骤进行计算：
f(1)=1
f(2)=2
f(3)=f(2)+f(1)=2+1=3
f(4)=f(3)+f(2)=3+2=5
f(5)=f(4)+f(3)=5+3=8
f(6)=f(5)+f(4)=8+5=13
f(7)=f(6)+f(5)=13+8=21
f(8)=f(7)+f(6)=21+13=34
f(9)=f(8)+f(7)=34+21=55
f(10)=f(9)+f(8)=55+34=89
所以，总共有89种不同的方法可以爬到第10级楼梯。

动态规划运筹学例题动态规划是运筹学中常用的一种优化技术，它利用规划、三角函数和其他数学技术来解决日常生活中的各种问题，比如最优路线问题、最优资源分配问题、最优出行路线问题等。

本文将通过一个例题，来介绍动态规划的基本思想，以及如何利用动态规划来解决问题。

例题一：已知一条路线，由A点到B点，有N个途经的节点，每个节点之间的距离已知。

求从A到B的最短路线。

按照动态规划的思想，首先将该问题分解为若干个子问题，并根据子问题的解来解决原问题，这种分解和解决问题的方式称为动态规划。

对于上面的问题，可以将其分解为N个子问题，分别是从A到第1个节点、从第1个节点到第2个节点、从第2个节点到第3个节点，以此类推，最后一个子问题是从第N-1个节点到B点的最短路程。

将上面的N个子问题中，从第i个节点到B点的最短路程记为d[i]，由于从第i个节点到B点可能经过i+1、i+2、……、N-1节点，因此要找到d[i]，只需要找到经过i+1、i+2、……、N-1节点的最短路程即可，即求d[i]=Min{d[i+1]+length[i][i+1],d[i+2]+length[i][i+2],…,d[N-1]+length[i][N-1]}，其中length[i][j]是第i个节点到第j个节点的距离。

以上就是动态规划的解题步骤，它能将原问题分解成若干个子问题，并找到最优解。

对于本例来说，通过上述步骤，就可以得到从A 到B的最短路程。

这种分解和求解问题的方法是动态规划，可以用来解决许多类似的问题，如：1）最优路线问题；2）旅行推销员问题；3）硬币找零问题。

动态规划的一大特点是，他能很好地将问题分解为多个子问题，并能从子问题的解中求解出最优解。

总之，动态规划是一种很有用的优化技术，它可以有效解决各种运筹学问题。

它不仅可以帮助我们解决许多具体问题，而且还能使我们更好地理解问题及其解法。

例1：机器负荷分配问题某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。

计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。

例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表：时期(k) 12 3 4 需要量(d k )2（单位）324假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为：若 0＜x ≤6 ， 则生产总成本＝3十1·x 若 x ＝0 ， 则生产总成本＝0又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。

现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元）年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年0 123 216 819 22第三年0122321185710192328第四年01232422191657101520243038第五年01234252320171446914202024303848试为该企业制定一个五年中的设备更新策略，使得企业在五年内总收益达到最大？例4：设有一辆栽重为10吨的卡车，用以装载三种货物，每种货物的单位重量及单件价值如表所示，问各种货物应装多少件，才能既不超过总重量又使总价值最大？货物 1 2 3单位重量 3 4 5单件价值 4 5 6。

动态规划练习题[题1] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。

现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。

顶行和底行的差值是2。

这个差值是两行点数之和的差的绝对值。

每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。

对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

输入格式：文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。

接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。

第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。

输出格式：只有一个整数在文件的第一行。

这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

[题2] Perform巡回演出题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入: 样例输出：3 6 4602 130 150 03 75 0 807 120 110 0 100 110 120 04 60 70 60 503 0 135 1402 70 802 32 0 701 800 0[题3] 复制书稿（BOOKS）问题描述：假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。

Floyd算法是一种用来寻找图中所有节点对之间最短路径的算法，它的核心思想是动态规划。

Floyd算法的基本原理是：假设图中有n个节点，将所有节点对之间的最短路径长度初始化为它们之间的直接连线长度，然后逐步更新这些距离，直到得到所有节点对之间的最短路径。

在本文中，我们将通过四个例题a1、a2、a3、a4来讲解Floyd算法的具体应用，以帮助读者更好地理解和掌握这一算法。

1. 例题a1【题目】有一个带权有向图，节点数为n，边数为m，求图中任意两点之间的最短路径长度。

【输入】第一行为两个整数n和m，分别表示节点数和边数。

接下来m行，每行包含三个整数a、b、c，表示图中存在一条从节点a到节点b的有向边，边的权值为c。

【输出】输出一个n×n的矩阵，其中第i行第j列的元素表示节点i到节点j的最短路径长度。

如果两点之间不存在路径，则输出一个特定的值（例如9999）。

【样例】输入：5 71 2 21 3 32 3 22 4 53 4 13 5 64 5 3输出：0 2 3 7 99999 0 2 5 89999 9999 0 3 69999 9999 9999 0 39999 9999 9999 9999 0【分析】根据给定的图和节点数，首先初始化一个n×n的矩阵，然后将直接连线的路径长度填入矩阵中。

接下来，利用Floyd算法逐步更新矩阵中的最短路径长度，直到得到所有节点对之间的最短路径长度。

2. 例题a2【题目】有一个带权有向图，节点数为n，边数为m，求图中是否存在负权环。

【输入】第一行为两个整数n和m，分别表示节点数和边数。

接下来m行，每行包含三个整数a、b、c，表示图中存在一条从节点a到节点b的有向边，边的权值为c。

【输出】若存在负权环，则输出"存在负权环"，否则输出"不存在负权环"。

【样例】输入：3 31 2 -12 3 -23 1 -3输出：存在负权环【分析】我们可以利用Floyd算法求出图中任意两点之间的最短路径长度，然后再验证是否存在负权环。

floyd算法的例题讲解Floyd算法，也称为Floyd-Warshall算法，是一种用于解决所有点对最短路径问题的动态规划算法。

它能够找出图中任意两个节点之间的最短路径，并计算出最短路径的长度。

下面以一个具体的例题来讲解Floyd算法的应用。

假设我们有一个带权有向图，表示城市之间的道路网络，图中的节点表示城市，边上的权重表示两个城市之间的距离。

我们的目标是找出任意两个城市之间的最短路径。

给定以下带权有向图的邻接矩阵表示：A B C DA 0 3 ∞7B ∞0 2 ∞C 5 ∞0 1D ∞∞12 0其中，∞表示两个城市之间没有直接的道路连接。

我们可以使用Floyd算法来解决这个问题。

首先，我们初始化一个与邻接矩阵相同的矩阵，称为距离矩阵。

初始时，距离矩阵的值等于邻接矩阵的值。

接下来，我们使用三重循环来逐步更新距离矩阵的值。

循环变量k表示中转节点，i和j 表示起点和终点。

具体的算法步骤如下：对于每对节点i和j，如果存在中转节点k，尝试更新距离矩阵的值：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

重复执行步骤1，直到遍历完所有的节点对(i, j)和中转节点k。

按照上述算法步骤，我们来计算最短路径的距离矩阵。

初始时，距离矩阵与邻接矩阵相同。

对于k = A：更新dist[A][B] = min(dist[A][B], dist[A][A] + dist[A][B]) = min(∞, 0 + 3) = 3。

更新dist[A][C] = min(dist[A][C], dist[A][A] + dist[A][C]) = min(∞, 0 + ∞) = ∞。

更新dist[A][D] = min(dist[A][D], dist[A][A] + dist[A][D]) = min(∞, 0 + 7) = 7。

对于k = B：更新dist[B][A] = min(dist[B][A], dist[B][B] + dist[B][A]) = min(∞, 0 + ∞) = ∞。

动态规划算法的常见实例动态规划算法是一种将复杂问题分解为简单子问题来解决的算法，它可被应用于多个领域中，如经济学、生物学、计算机科学等。

在本文中，我们将详细讨论动态规划算法的常见实例。

一、最长公共子序列问题最长公共子序列（LCS）问题是一个经典的计算机科学问题，它要求在两个字符串中找到最长的相同连续子序列。

例如，对于字符串“ABCD”和“ACDF”，最长公共子序列为“ACD”。

使用动态规划方法来解决LCS问题。

首先定义一个m行n列的二维矩阵，其中m和n分别表示两个字符串的长度。

然后，使用以下递推关系：1. 如果一个字符串的长度为0，LCS为0。

2. 如果两个字符不相同，则LCS为它们的前一个字符集合和它们的后一个字符集合的最大值。

3. 如果两个字符相同，则LCS为它们的前一个字符集合和它们的后一个字符集合所组成的子序列中的最大值加1。

最后，矩阵右下角的值就是LCS的长度。

二、背包问题背包问题（Knapsack problem）是一个经典的组合优化问题，被广泛应用于计算机科学和其他领域。

在一个决策者必须决定是否将某些物品放入背包中的场景中，背包问题就发挥了作用。

具体来说，我们要解决的问题是：对于一个固定容量的背包，有一些物品，它们的重量和价值都不同，如何在不超过背包容量的前提下，使所装载物品的总价值最大化。

一种解决方案是使用动态规划方法。

定义一个二维数组，其行表示物品，列表示背包大小。

然后，使用以下递推关系：1. 如果所考虑的物品重量大于背包容量，则不选此物品。

2. 否则，在选取该物品和不选该物品两种情况中选择最优解作为最终结果。

最后，矩阵中右下角的值就是最大的总价值。

三、矩阵链乘法矩阵链乘法是一种计算矩阵乘积的优化算法。

它使用动态规划算法来确定矩阵乘积的最小值。

对于一个长度为n的矩阵链，我们可以定义一个n×n 的矩阵M，其中第i行第j列的元素Mi，j表示第i个矩阵与第j个矩阵相乘的最小次数。

动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。

（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。

⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。

⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。

动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。

这样就能够从表中得到原始问题的解。

（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。

关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。

⽽在各阶段中。

⼈们都须要作出⽅案的选择。

我们称之为决策。

⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。

这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。

因为各个阶段可供选择的决策往往不⽌⼀个。

因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。

每⼀个策略都对应地确定⼀种活动的效果。

我们假定这个效果能够⽤数量来衡量。

因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。

经常是⼈们所关⼼的问题。

我们称这种策略为最优策略，这类问题就称为多阶段决策问题。

（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。

在⾼负荷下⽣产时。

产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y的关系为h=h(y)。

常见动态规划题⽬详解1.爬楼梯题⽬描述：假设你正在爬楼梯。

需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。

你有多少种不同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数。

⽰例 1：输⼊： 2输出： 2解释：有两种⽅法可以爬到楼顶。

1. 1 阶 + 1 阶2. 2 阶⽰例 2：输⼊： 3输出： 3解释：有三种⽅法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶实现代码：class Solution {public:int climbStairs(int n) {vector<int> a(n);a[0] = 1;a[1] = 2;if(n == 1){return 1;}if(n == 2){return 2;}for(int i = 2; i < n;i++){a[i] = a[i - 1] + a[i - 2];}return a[n - 1];}};2.变态跳台阶题⽬描述：⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。

求该青蛙跳上⼀个n级的台阶总共有多少种跳法。

实现代码：class Solution {public:int jumpFloorII(int number) {if(number == 0){return 0;}int total = 1;for(int i = 1; i < number; i++){total *= 2;}return total;}};3.n年后⽜的数量题⽬描述：假设农场中的母⽜每年会产⽣⼀头⼩母⽜，并且永远不会死。

第⼀年农场中只有⼀头成熟的母⽜，第⼆年开始，母⽜开始⽣⼩母⽜，每只⼩母⽜三年之后成熟⼜可以⽣⼩母⽜，给定整数N，求N年后母⽜的数量。

实现代码：class solution{　public: int f(int n){ if(n < 1){ return 0; } if(n == 1|| n== 2||n == 3){ return n; } int res = 3; int pre = 2; int prepre = 1; int tmp1=0; int tmp2 = 0; for(int i = 4;i < n;i++){ tmp1 = res; tmp2 = pre; res = pre + prepre; pre = tmp1; prepre = tmp2; } return res; }};4.矩形覆盖题⽬描述：我们可以⽤2*1的⼩矩形横着或者竖着去覆盖更⼤的矩形。

动态规划算法题（5题）1、题⽬描述（⽹易）有 n 个学⽣站成⼀排，每个学⽣有⼀个能⼒值，⽜⽜想从这 n 个学⽣中按照顺序选取 k 名学⽣，要求相邻两个学⽣的位置编号的差不超过d，使得这 k 个学⽣的能⼒值的乘积最⼤，你能返回最⼤的乘积吗？输⼊描述:每个输⼊包含 1 个测试⽤例。

每个测试数据的第⼀⾏包含⼀个整数 n (1 <= n <= 50)，表⽰学⽣的个数，接下来的⼀⾏，包含 n 个整数，按顺序表⽰每个学⽣的能⼒值 ai（-50 <= ai <= 50）。

接下来的⼀⾏包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:输出⼀⾏表⽰最⼤的乘积。

试题分析：本题要使⽤动态规划来解，动态规划的特点：1.求解的是最优化问题；2.可以分解为最优⼦结构本题可以先求解在第i个学⽣的位置下，j（j<K）个学⽣的能⼒值的最⼤值，得到所有学⽣位置下j个学⽣的能⼒值的最⼤值；在j个学⽣的情况下，得到j+1个学⽣的最⼤值，样例输出： 10 8 7 2 -7 9 5 4 10 -7 1 3 3输出： 630如上，第⼀步先计算k=2的情况：7:在d=3的情况下，最⼤最⼩值都为562:在d=3的情况下，最⼤值为16，最⼩值为14-7:在d=3的情况下，最⼤值为-14，最⼩值为-56......得到第⼀趟的结果k=3的情况下（这⾥以第⼀趟的结果为基础，只有这样就不需要考虑第⼀趟中d=3的限制）：2:在d=3的情况下，最⼤最⼩值都为112（56*2）-7:在d=3的情况下，最⼤值为-98（14*-7）最⼩值为-392（56*-7）9:在d=3的情况下，最⼤值为504（56*9）最⼩值为-504（-56*9）......得到第⼆趟的结果返回最⼤值就是最后的结果#-*- coding:utf-8 -*-n=input()array=[int(i) for i in raw_input().split()]k,d=[int(i) for i in raw_input().split()]# n=36array_max=array_min=array#轮询k-1趟即可for i in range(0,k-1):_max=[-float('inf')]*n#将最⼤值的数组赋值⽆穷⼩_min=[float('inf')]*n#将最⼩值的数组赋值⽆穷⼤for j in range(i+1,n):if j<=d+i:#下⾯对应的min、max都是考虑到array[j]为负值的情况下temp_max = max(max(ii*array[j] for ii in array_max[i:j]),max(ii*array[j] for ii in array_min[i:j]))temp_min = min(min(ii*array[j] for ii in array_max[i:j]),min(ii*array[j] for ii in array_min[i:j]))else:temp_max = max(max(ii*array[j] for ii in array_max[j-d:j]),max(ii*array[j] for ii in array_min[j-d:j]))temp_min = min(min(ii*array[j] for ii in array_max[j-d:j]),min(ii*array[j] for ii in array_min[j-d:j]))_max[j]=temp_max_min[j]=temp_minarray_max=_maxarray_min=_minprint array_maxprint array_minprint max(array_max)2、题⽬描述（腾讯）：腾讯⼤厦有39层，你⼿⾥有两颗⼀抹⼀眼的玻璃珠。

力扣优秀题解——动态规划动态规划（Dynamic programming，简称DP）是一种常见的求解优化问题的方法。

它与分治算法类似，都是通过将大问题分解成若干个小问题来求解的。

不同的是，DP解决的问题通常是有重叠子问题和最优子结构特征的，即在求解过程中会反复计算相同的子问题，并且每个子问题都具有最优解，可以通过这些最优解推导出全局最优解。

力扣中的很多题目都可以使用动态规划来解决，比如最长公共子序列、股票买卖、打家劫舍等等。

下面针对这些题目进行详细解析。

一、最长公共子序列题目描述：给定两个字符串text1 和text2，返回它们的最长公共子序列。

如果不存在公共子序列，返回0。

示例：输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。

解题思路：最长公共子序列问题是比较经典的DP问题。

设字符串text1和text2的长度分别为m 和n，令dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度，为方便起见，text1和text2的下标从1开始。

当text1[i-1] == text2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1，即text1[0:i-1]和text2[0:j-1]的最长公共子序列长度加上1。

当text1[i-1] != text2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即考虑text1[0:i-1]和text2[0:j]的最长公共子序列长度与text1[0:i]和text2[0:j-1]的最长公共子序列长度，两者取最大值。

最终的答案即为dp[m][n]。

代码实现：class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]二、股票买卖题目描述：给定一个数组prices，其中prices[i]是一支给定股票第i天的价格。