12个动态规划算法举例（动态规划算法详解及例题）

本篇文章给大家谈谈12个动态规划算法举例，以及动态规划算法详解及例题对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、Python之动态规划算法
• 2、生物学中常用的两种动态规划算法
• 3、动态规划算法怎么计算？
• 4、求动态规划计数例题
• 5、动态规划
• 6、动态规划算法详解

Python之动态规划算法

动态规划算法中是将复杂问题递归分解为子问题，通过解决这皮拆些子问题来解决复杂问题。与递归算法相比，动态编程减少了堆栈的使用，避免了重复的计算，效率得到显著提升。

先来看一个简单的例子，斐波那契数列.

斐波那契数列的定义如下。

斐波那契数列可以很容易地用递归算法实现：

上述代码，随燃旁枣着n的增加，计算量呈指数级增长，算法的时间复杂度是 。

采用动态规划算法，通过自下而上的计算数列的值，可以使算法复杂度减小到 ，代码如下。

下面我们再看一个复杂一些的例子。

这是小学奥数常见的硬币问题： 已知有1分，2分，5分三种硬币数量不限，用这些硬币凑成为n分钱，那么一共有多少种组合方法。

我们将硬币的种类用列表 coins 定义；

将问题定义为一个二维数组 dp，dp[amt][j] 是使用 coins 中前 j+1 种硬币( coins[0:j+1] )凑成总价amt的组合数。

例如： coins = [1,2,5]

dp[5][1] 就是使用前两种硬币 [1,2] 凑成总和为5的组合数。

对于所有的 dp[0][j] 来说，凑成总价为0的情况只有一种，就是所有的硬币数量都为0。所以对于在有效范围内任意的j，都有 dp[0][j] 为1。

对于 dp[amt][j] 的计算，也就是使用 coins[0:j+1] 硬币总价amt的组合数，包含两种情况计算：

1.当使用第j个硬币时，有 dp[amt-coins[j]][j] 种情况，即amt减去第j个硬币币值，使用前j+1种硬币的组合数；

2.当不使用第j个硬币时，有 dp[amt][j-1] 种情况，即使用前j种硬币凑成amt的组合数；

所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]

我们最终得到的结果是：dp[amount][-1]

上述分析省略了一些边界情况。

有了上述的分析，代码实现就比较简单了。

动态规划算法代码简洁，执行效率高。但是与递归算法相比，需要仔细考虑如何分解问题，动态规划代码与递归调用相比，较难理解。

我把递归算法启瞎实现的代码也附在下面。有兴趣的朋友可以比较一下两种算法的时间复杂度有多大差别。

上述代码在Python 3.7运行通过。

生物学中常用的两种动态规划算法

动态规划算法(Dynamic Programming Algorithm)是一种计算方法，它的主要思路是把一个问题分成若干个小问题来解决

在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局部比对）

（1）全局序列比对：

1）两条序列可以在一个x- 和y-轴的矩阵中得到比对；

2）如果序列一致，则可以得到一条通过对角线的路径；

3）寻找最佳的次路径，然后将它们加起来得到最好的得分，

这包括：

需要时插入空隙（gap）

允许保守替代

选择打分系统（简单的或复杂的）

Needleman-Wunsch算法可以保证得到最佳纳宏的比对

（2）局部序列比对：局部比对的目标是寻找两序列最优比对区（子序列），不需要延伸到序列的两端；局部比对是数据库搜索是最常用的算法，在寻找序列之间的结构域时相当有用。 1）Smith-Waterman 算洞祥册法

1. 设置一个矩阵，大小为（m+1, n+1）

2. 矩阵中的值必须不小于0。

3. 矩阵中的每个单元格的分值S是以下四者中的最大值：

1. 算法的目的是寻找矩阵中的最大值，这代表了比对中的结尾处（羧基端）。

2. 回溯过程从最大值的位置开始，沿着对角线向上向左直到碰到一个零分值的单元格。

3. 算法需要的一个条件是随机匹配的期望分值为负，保证不相关的长序列不能得宴陪到高分值（大多打分矩阵满足此条）

动态规划算法怎么计算？

动态规划算法：

（1）分析最优解的性质，并刻画其结构特征。

（2）递归的定义最优解。

（3）以自底向衡悉掘上或自顶向下的记忆化方式（备忘录法）计算出最优值。

（4）根据计算最优值时陆拆得到的信息，构造问题的最优解。

动态规划与其它算法相比，大大减少了计算量，丰富了计算结果，不仅求出了当前状态到目标状态的最优值，而且同时求出了到中间状态的最优值，这对于很多实际问题来说是很有用的。动态规划相比一般算法也存在一定缺点:空间占据过多，但对于空咐核间需求量不大的题目来说，动态规划无疑是最佳方法!动态规划算法和贪婪算法都是构造最优解的常用方法。动态规划算法没有一个固定的解题模式，技巧性很强。

求动态规划计数例题

这是我们计算机系算法设计课的实验课程，下面是动态规划内容：

实验四：动态规划

实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。

实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。

习题

1． 最长公共子序列

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=x1, x2,…, xm，则另一序列Z=z1, z2,…, zk是X的子序列是指存在一个严格递增的下标序列 i1, i2,…, ik，使得对于所有j=1,2,…,k有

解答如下：

a) 最长公共子序列的结构

若用穷举茄虚搜索法，耗时太长，算法需要指数时间。

易证最长公共子序列问题也有最优子结构性质

设序列X=x1, x2, …, xm和Y=y1, y2, …, yn的一个最长公共子序列Z=z1, z2, …, zk，则：

i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；

ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；

iii. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=x1, x2, …, xm-1，Yn-1=y1, y2, …, yn-1，Zk-1=z1, z2, …, zk-1。

最长公共子序列问题具有最优子结构性质。

b) 子问题的递归结构

由最长公共子序列问题的最优子结构性质可知，要找出X=x1, x2, …, xm和Y=y1, y2, …, yn的最长公共子序列，可按以下方式递归地进行：当xm=yn时，唯源找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。

我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1, x2, …, xi，Yj=y1, y2, …, yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：

c) 计算最优值

由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=x1, x2, …, xm和Y=y1, y2, …, yn作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子指纳态序列的长度记录于c[m,n]中。

程序如下：

#includestdio.h

#includestring.h

int lcs_length(char x[], char y[]);

int main()

{

char x[100],y[100];

int len;

while(1)

{

scanf("%s%s",x,y);

if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束

break;

len=lcs_length(x,y);

printf("%d\n",len);

}

}

int lcs_length(char x[], char y[] )

{

int m,n,i,j,l[100][100];

m=strlen(x);

n=strlen(y);

for(i=0;im+1;i++)

l[i][0]=0;

for(j=0;jn+1;j++)

l[0][j]=0;

for(i=1;i=m;i++)

for(j=1;j=n;j++)

if(x[i-1]==y[j-1]) //i,j从1开始，但字符串是从0开始

l[i][j]=l[i-1][j-1]+1;

else if(l[i][j-1]l[i-1][j])

l[i][j]=l[i][j-1];

else

l[i][j]=l[i-1][j];

return l[m][n];

}

由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。

思考：空间能节约吗？

2． 计算矩阵连乘积

在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：

现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。

递归公式：

程序如下：

#includestdio.h

int main()

{

int p[101],i,j,k,r,t,n;

int m[101][101]; //为了跟讲解时保持一致数组从1开始

int s[101][101]; //记录从第i到第j个矩阵连乘的断开位置

scanf("%d",n);

for(i=0;i=n;i++)

scanf("%d",p[i]); //读入p[i]的值(注意：p[0]到p[n]共n+1项)

for(i=1;i=n;i++) //初始化m[i][i]=0

m[i][i]=0;

for(r=1;rn;r++) //r为i、j相差的值

for(i=1;in;i++) //i为行

{

j=i+r; //j为列

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; //给m[i][j]赋初值

s[i][j]=i;

for(k=i+1;kj;k++)

{

t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(tm[i][j])

{

m[i][j]=t; //m[i][j]取最小值

s[i][j]=k;

}

}

}

printf("%d",m[1][n]);

}

3． 凸多边形的最优三角剖分

多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。

通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=v0 ,v1 ,… ,vn-1表示具有n条边v0v1，v1v2，… ,vn-1vn的一个凸多边形，其中，约定v0=vn 。

若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形vi ,vi+1 ,… ,vj和vj ,vj+1 ,… ,vi。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。

凸多边形最优三角剖分的问题是：给定一个凸多边形P=v0 ,v1 ,… ,vn-1以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。

可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数)

4． 防卫导弹

一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：

a)它是该次测试中第一个被防卫导弹截击的导弹；

b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。

输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。

输出数据：截击导弹的最大数目。

分析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。

由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个j，满足h[j]=h[i]的j中l[j]的最大值。

程序如下：

#includestdio.h

int main()

{

int i,j,n,max,h[100],l[100];

scanf("%d",n);

for(i=0;in;i++)

scanf("%d",h[i]);

l[n-1]=1;

for(i=n-2;i=0;i--)

{

max=0;

for(j=i+1;jn;j++)

if(h[i]h[j]maxl[j])

max=l[j];

l[i]=max+1;

}

printf("%d",l[0]);

}

5． 石子合并

在一个圆形操场的四周摆放着n堆石子(n= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(=20)。

选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；

输入数据：

第一行为石子堆数n；

第二行为每堆的石子数,每两个数之间用一个空格分隔。

输出数据：

从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1=i=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。

Sample Input

4

4 5 9 4

Sample Output

－4 5 9 －4

－8 －5 9

－13 －9

22 4 －5 －9 4

4 －14 －4

－4 －18

22

6． 最小代价子母树

设有一排数，共n个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。

输入、输出数据格式与“石子合并”相同。

Sample Input

4

12 5 16 4

Sample Output

－12 －5 16 4

17 －16 －4

－17 －20

37

7． 商店购物

某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。

编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU因为：

1朵花加2个花瓶优惠价：10 ICU

2朵花正常价：4 ICU

输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。

第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。

第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。

输出数据：在输出文件OUTPUT．TXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。

8． 旅游预算

一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：

若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。

输入数据：从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况：

第一行为起点到终点的距离（实数）

第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。

输出数据：答案输出到当前目录下的文本文件“route.out”中。该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。

Sample Input

516.3 38.09 1

15.7 22.1 20.87 3 2

125.4 1.259

297.9 1.129

345.2 0.999

Sample Output

38.09 1

2

9． 皇宫看守

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入数据：输入数据由文件名为intput.txt的文本文件提供。输入文件中数据表示一棵树，描述如下：

第1行 n，表示树中结点的数目。

第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0i=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。

对于一个n（0 n = 1500）个结点的树，结点标号在1到n之间，且标号不重复。

输出数据：输出到output.txt文件中。输出文件仅包含一个数，为所求的最少的经费。

如右图的输入数据示例：

Sample Input

6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0

Sample Output

25

10． 游戏室问题

有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于等于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到多少的快乐。

11． *基因问题

已知两个基因序列如s：AGTAGT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出：

A G C T 〕

A 5 -2 -1 -2 -4

G -2 5 -4 -3 -2

C -1 -4 5 -5 -1

T -2 -3 -5 5 -2

〕 -4 -2 -1 -2

提示：定义问题l[i][j]为取第一个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值与三个子问题有关，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。

建立递归公式如下：

其中m[0][t[j]表示表中空格和t[j]匹配的对应值。

思考：本问题的初始化。

12． *田忌赛马

田忌与齐王赛马，双方各有n匹马参赛（n=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。

分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：

若田忌的马快，就让这两匹马比赛；

若田忌的马慢，干脆就让他对付齐王最快的马；

若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。

定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。

则：

程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。

程序如下：

#includestdio.h

void readdata();

void init();

int n,a[100],b[100],l[100][100];

int main()

{

int i,j;

readdata();

init();

for(i=n-2;i=0;i--)

for(j=1;jn-i;j++)

if(a[i+j]b[j])

l[i][j]=l[i][j-1]+1;

else if(a[i+j]b[j])

l[i][j]=l[i+1][j-1]-1;

else if(l[i+1][j-1]-1l[i][j-1])

l[i][j]=l[i+1][j-1]-1;

else

l[i][j]=l[i][j-1];

printf("%d",l[0][n-1]);

}

void readdata()

{

int i;

scanf("%d",n);

for(i=0;in;i++)

scanf("%d",a[i]);

for(i=0;in;i++)

scanf("%d",b[i]);

}

void init()

{

int i;

// qsort(a,n); //略

for(i=0;in;i++)

{

if(a[i]b[0])

l[i][0]=1;

else if(a[i]==b[0])

l[i][0]=0;

else

l[i][0]=-1;

}

}

动态规划

与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解）

例： 背包问题之动态规划解决

问题描述：

现在有一个背包可以装4磅物品，现在要从商城里拿尽可能价值高的物品装进包里。

商城物品情况如下

每个动态规划都从一个网格（如下）开始

现在一行一行地填充该网格。

每个格子的计算公式：

填充吉他行 目前最大价值1500（吉他）

填充音箱：目前最大价值3000（音箱）

填充笔记本：目前最大价值3500（吉他+笔记本）

动态规划的原则就是将大问题拆解成多个小问题，先把小问题的最优解求出，再在考虑小问题最优解的前提下，得出最终问题的最优解

本例的背包问题中，先求出只有吉他一种物品时的最优解，再逐步添加物品，最终求出最优解

关于网格计算公式的补充：

整个动态规划求解过程中，是从小问题层逐步求解到大问题，自然每个格子要考虑的第一点就是前一格子的最大值，又，新的一层添加了新物品，所有也要考虑新物品的价值+剩余可用磅数的最大价值（上一层求得）

背包问题补充：

若再添加一个物品 ——项链{‘价值’：1000$，‘重量’：0.5磅}

此时如果沿用之前的网格

如果要装的物品为燕麦，木豆，大米 这种可以一部分一部分取出的物品

动态规划则解决不了这种情形，贪心可以。

旅游行程问题

当然我们可以用动态规划的网格法来得到一条最有价值的旅游路线

如果加入以下景点

在去巴黎的景点所花费的时间中，有0.5天是从伦敦前往巴黎的时间。

因此如果先去了埃菲尔铁塔,则去巴黎的剩下两个景点的花费时间也要减少2个小时

这种情况就不能使用之前的动态规划算法。宽轿

动态算法处理的每个子问题都是离散的

再来看一个案例

假如你要经营一个网站，网站主要任务是：英文单词翻译。即用户输入英文单词，你给出相应的翻译。 例用户输入fish，网站输出鱼

如果用户输入的hish，但词典中并没有该单词，此时应给出相似词。

怎么样才算是相似词呢？判断最大子串长度？

利用动态规划求出两字符串（fish和hish）的最大字串长度

动态规划解决问题总是要先知道网格中的各个元素：

两个坐标轴是什么？网格中的值是什么（通常为要 优化的指标 ）

1，分解问题：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）。考虑两个坐标轴为两个单词，则网格中的值为最大子串的长度。

接下来填充该网格。不断验证得到单元格公式：

单元格公式解释：

1）两字母相同，则局部最大字串要延长，即斜上方（cell[i][j]）的值加一(这里指标值在斜方向上累加)

2）若是不同，则局部最大字串为0

两字符串的最大字串长度即为网格中的最大值3。

如果用户输入fosh，那么要返回fish还是fort呢？

如果判断依据为手纳最大毕巧没子串，则会返回fort，但实际上fish和fosh更像！

因此我们考虑判断依据为两字符串的最大公共子序列长度（即两字符串公共字符的个数）

求最大公共子序列的单元格公式为：

fosh和fort的最大公共子序列长度为2

fosh和fish的最大公共子序列长度为3

此时就可以返回正确结果fish而非fort。

1，动态规划通常用于解决 在给定约束条件下优化某个指标值

2，动态规划的原则就是：将大问题分解成小问题，在解决了小问题的条件下，逐步求解大问题。（一个分解问题的方法就是，将条件逐渐减少，从最简单的情况开始分析）

3，动态规划使用的一个必要条件为： 分解出来的每个小问题都是离散的

4，每种动态规划方案都设计网格

4.1，网格的每个格子都是一个小问题

4.2，网格的每个格子的值都是指标的值

4.3，单元格计算公式需要 具体问题具体分析 。

[img]

动态规划算法详解

动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。

将待求解问题分解成若干个子拍氏问题，先求解子问题，然后从这些子问题的解得到原问题的解（这部分与分治法相似）。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，袭铅散而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。通常可以用一个表来记录所有已解的子问题的答案。

问题的一个最优解中所包含的子问题的解也是最优的。总问题包含很多个子问题，而这些子问题的解也是最优的。

用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单激搏地查看一下结果，从而获得较高的效率。

：很显然，这道题的对应的数学表达式是

其中F(1)=1, F(2)=2。很自然的状况是，采用递归函数来求解：

参考：

关于12个动态规划算法举例和动态规划算法详解及例题的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。