软考-算法设计概述及常见的几种算法形式

向右看齐 2021-09-08 06:12 336阅读 0赞

## 递归法 ##

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题转化为一  
个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。  
递归算法一般用于解决三类问题：  
（1）数据的定义是按递归定义的。（Fibonacci函数）  
（2）问题解法按递归算法实现。（回溯）  
（3）数据的结构形式是按递归定义的。（树的遍历，图的搜索）  
递归的执行过程可分为分解和求值两部分。首先是逐步把"大问题”分解成形式相同但规模很小的"小问题"，直至分解到递归出口。一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是量变过程，即原来的大问题，在慢慢变小，但尚未解决。遇到递归出口后，便发生了"质变"，即原递归问题转换成直接可以求值的简单问题。  
递归只需要少量的步骤就可描述解题过程中所需要的多次重复计算，极大地减少了代码量。该算法设计的关键  
在于，找出递归方程和边界条件（递归出口）。递归关系就是使问题向边界条件转化的过程，所以递归关系必须能使问题越来越简单，规模越小。没有设定边界的递归是死循环。  
递归算法设计通常需要按照以下3个步骤：  
（1）分析问题，得出递归关系；  
（2）设置边界条件，控制递归；  
（3）设计函数，确定参数。  
求解Fibonacci数列的第n项函数Fibonacci（n）就是一个典型的例子。Fibonacci数列为：  
1，1，2.3.5.813，21…  
即 Fibonacci（1）=1；  
Fibonacci（2）=1；  
Fibonacci（n）= Fibonacci（n-1）+ Fibonacci（n-2）  
（当n22时）。  
根据递归公式，很容易得出递归函数：

int Fibonacci（intn）
    if（n<1）//预防错误
    return 0；
    if（n==111 n ==2）//设置边界条件
    return 1；
    return Fibonacci（n-1）+ Fibonacci（n-2）；

需要说明的是上边的例子并不是递归方法的最佳例子，因为在n足够大时，则程序将变得缓慢甚至可能将计算机的内存耗尽。因此，在类似问题求解时，应限制n的最大值。  
又如楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编写程序计算共有多少种不同的走法。例如，当n-3时，共有3种走法，即1+1+1，1+2，2+1，当n-4时，共有5种走法，即1+1+1+1，2+2，2+1+1，1+2+1，1+1+2，算法分析：设n阶台阶的走法数为（n），显然有  
(1) f(1)=1 n=1;  
(2) f(2)-2 n=2;  
(3) f(n)=f(n-1 )+ f(n-2) n> 2.

得到相应的函数如下：

int Fstairs（int n）{
    if（n ==111n ==2）
    	return n ;
    return Fstairs（n-1）+ Fstairs（n-2）；}

再如Hanoi Tower问题：设A，B，C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自上而下，由小到大地叠在一起。各圆盘从小到大编号为1，2，.，n，现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。  
在移动圆盘时应遵守以下移动规则：  
（1）每次只能移动1个圆盘；  
（2）任何时刻都不允许将较大的圆盘压在较小的圆盘之上；  
(3）在满足移动规则1和2的前提下，可将盘移至A，B，C中任一塔座上。  
算法分析：这是一个典型的适合用递归算法来解决的问题。  
试想要把n个盘子从柱A移到柱C上，则必须先把上面n-1个盘子从柱A全部移到柱B，然后把第n个盘子由柱A移到柱C，再把柱B上的n-1个盘子全部移到柱C。这样就把移动n个盘子的问题变成了移动n-1个盘子的问题，如此不断减小递归的规模，直到递归出口。  
递归的边界条件是，当n==1时，直接把它由柱A移到柱C.  
1汉诺塔，把柱A所有的盘子移到柱C  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]  
从上述的3个例子中我们可以发现，递归算法具有以下三个基本规则：  
（1）基本情形：至少有一种无需递归即可获得解决的情形，也即前面说的边界条件。（2）进展：任意递归调用必须向基本情形迈进，即前面所说的使得问题规模变小。  
（3）正确性假设：总是假设递归调用是有效的。  
递归调用的有效性是可以用数学归纳法证明的，所以当我们在设计递归函数时，不必设法跟踪可能很长的递归调用途径（比如Hanoi Tower问题）。这种任务可能很麻烦，易于使设计和验证变得更加困难。所以我们一旦决定使用递归算法，则必须假设递归调用是有效的。

与递归相对应的递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。递推算法以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从"起点"重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）先一步的结果。

在算法设计时，能用递推实现的算法一般都可以用递归来实现。能用递归实现的算法不一定能够通过递推实现。就算法的效率而言，递推优于递归。

## 贪心法 ##

贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。金心法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况。

在求最优解问题的过程中，依据某种金心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。

从贪心算法的定义可以看出，贪心算法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法是否可以得到最优解。

如均分纸牌问题。有N堆纸牌，编号分别为1，2，N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为：9，8，17，6。设a1为第堆纸牌的张数（O<-ik=n），V为均分后每堆纸牌的张数，s为最小移到次数。用金心法按照从左到右的顺序移动纸牌。如第堆（0xikn）的纸牌教a1不等于平均值，则移动一次（即s加1），分两种情况移动：

（1）若al>v，则将ali-v张纸牌从第堆移动到第1+1堆；  
（2）若all<sv，则将v-al）张纸牌从第1+ 1堆移动到第谁；上述两种情况可以统一看作是将ali-v张牌从第堆移动到第1+1堆；移动后有：alj-v；ali+1\]-a1i+1\]+al-v；在从第11堆中取出纸牌补充第堆的过程中，可能会出现第1+1堆的纸牌数小于零（ali+1+ali-v<0）的情况。如n-3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移。  
从第二堆移出9张到第一堆后，第一堆有10张纸脾，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。  
在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此，此题使用贪心法可以求解。

利用贪心法求解需要注意以下两点：  
（1）贪心法求解是否适合。  
用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，需要在平时多加练习，依据解题经验来判断是否适合使用会心算法。如下边的例子：以找而问题为例，如果一个货币系统有3种而值，面值分别为一角、五分和一分，求最小找币数时，可以用会心法求解；如果将这三种而值改为一角一分、五分和一分，就不能使用盒心法求解。  
（2）选择何种贪心标准才能保证求得最优解。  
在选择贪心标准时，要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的会心标准所迷感。如下面的例子：有N个正整数，将他们连接成一排，组成一个最大的多位整数。例如有3个正整数：13，5，20，则20513就是所求。又如13，131这2个正整数，连接组成最大的多位数是13131，分析后发现其会心标准为：把整数化成字符串，然后再比较a+b和b+a，如果a+b>bta，就把a排在b的前面，反之则把a排在b的后面。如果把金心标准设定为数值大的数放在前面，有时就会得到错误的结论，比如13，131这2个正整数，连接组成的多位数是13113，但这并不是最大的多位数。  
贪心法的基本原理是从问题的某一个初始解出发逐步通近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

因此，金心法存在以下问题：  
（1）不能保证求得的最后解是最优解；  
（2）不能用来求最大或最小解问题；  
（3）只能求满足某些约束条件的可行解的问题。  
利用贪心法解题，通常的解题思路为：  
（1）建立数学模型来描述问题；  
2）把求解的问题分成若干个子问题；  
（3）对每一子问题求解，得到子问题的局部最优解；  
（4）把子问题的解局部最优解合成原来解问题的一个解  
利用贪心法解题，通常的步骤为以下三步：  
（1）从问题的某一初始解出发；  
（2）循环求解，求出可行解的一个解元素；  
（3）由所有解元素组合成问题的一个可行解。

## 回溯法 ##

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。  
回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。  
树T类似于检索树，它可以这样构造：设Si中的元素可排成xi（1），xi（2），…，xi（mi-1），1sij =-mi，= 1，2，.n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1（1），xi+1（2），…xit（mi），i-0，1，2，…0-1.照这种构造方式，  
E中的一个n元组（x1，x2，…，x）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，.xn，反之亦然。  
另外，对于任意的0sisn-1，E中n元组（x1，x2，.xn）的一个前缀元组（x1，x2，.xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的条边的权分别为x1，x2，.xi，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。  
因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、.，前缀元组（x1，x2，.xi），.直到=n为止。  
在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。  
如找出从自然数1，2，…，n中任取个数的所有组合的问题。采用回溯法求问题的解，将找到的组合以从小到大顺序存于al0\]，a1\]，…\[f-1中，组合的元素满足以下性质：  
（1）ali+1>a11，后一个数字比前一个大；  
（2）al1-E-+1按回溯法的思想，求解过程可以分析如下：  
按回溯法的思想，求解过程可以分析如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并便其满足上述条件（1），候选组合改为1，2，继续这一过程，得到选组合1，2，3，该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a\[2\]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5，由于对5不能再作调整，就要从a\[2）回溯到a11\]，这时，a11j-2，可以调整为3，并向前试探，得到解1，3，4，重复上述向前试探和向后回溯，直至要从a\[0\]再回溯时，说明已经找完问题的全部解。示意代码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]  
又如古老而著名的n皇后问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8x8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆去。在国际象棋中，皇后是可以横走、直走、斜走的最强大的棋子。在一个8乘8的棋盘上，如何放置最多数量的皇后，使这些皇后互相不吃，由于每行每列最多只能一个皇后，所以最多只能8个皇后出现在一个8x8格的棋盘上。  
再如迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进：如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有的可能都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷言路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。  
回溯法其实就是试探的方法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。利用回湖法解题，通常可分为以下三个步骤：  
（1）针对所给问题，定义问题的解空间；  
（2）确定易于搜索的解空间结构；  
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

## 分治法 ##

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。  
例口，对于n个元素的排序问题，当n-1时，不需任何计算。n-2时，只要作一次比较即可排子序。n-3时，只要作3次比较即可。而当n较大时，问题就不那么容易处理了。  
要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。  
如果原问题可分割成个子问题，1cksn，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。  
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对李生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。  
分治法所能解决的问题一般具有以下几个特征：  
（1）该问题的规模缩小到一定的程度就可以容易地解决；  
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质：  
（3）利用该问题分解出的子问题的解可以合并为该问题的解  
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。  
绝大多数问题都具备上述的第1条特征，因为问题的计算复杂性一般是随着问题规模的增加而增加；第2条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第3条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。  
第4条特征涉及到纷治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但时在一般情况下，用动态规划法较好。  
如给定一个顺序表，编写一个求出其最大值和最小值的分治算法。由于顺序表的结构没有给出，作为演示分治法这里从简，设顺序表为一整形数组，数组大小由用户定义，数据随机生成。如果数组大小为1则可以直接给出结果，如果大小为2，则一次比较即可得出结果，于是我们找到求解该问题的子问题即：数组大小<=2。到此我们就可以进行分治运算了，只要求解的问题数组长度比2大就继续分治，否则求解子问题的解并更新全局解，这里以C代码为例：

#include<stdio.h>
    #include<stdib.h>
    #includexlimits h>
    #defineM401分治法获取最优解1
    voidPartionGet（int s，int e，int meter，int'max，in min）
    {
    /*参数
    "s当前分治段的开始下标
    "当前分治段的结束下标
    "meter表的地址
    "max存储当前搜索到的最大值
    'min存储当前搜索到的最小值1*/
    
    int i=1
     if（e-s <=1）{
    /*获取局部解，并更新全局解1*/
    if（meterfs）> meterje）
    if（metersj >"max）*max =meterfs
    if（metere]<min）*min =meterte]
    }else{
     if（meterfe]>*max）*max =meter[s]；
     if（meters）<*min）*min =meter[s];
     }
     return；
     }
     i = s+（e-s）/2；
     /*不是子问题继续分治，这里使用了二分，也可以是其它*/
     
     PartionGet（s，meter，max，min）
    PartionGet（i+1，e.meter，max，min）;
    }
    int main（）
    {
    int i，meter（M）；/*用最小值初始化*/
    int max = INT_MIN：/*用最大值初始化*/
    int min = INT-MAX print（"Thearray'selementasfollowed:'n"）；/*初始化随机数发生器*/
    randomize（）；
    for（i = 0;i<M;i++){
    /*随机数据填充数组*/
    meter = rand（）%10000；
    if（!((i1)%10)）
    /"输出表的随机数据*/
    printi（"%-d\n"，meter）；
    else print（"%-6d"，meter）；
    }
    PartionGet（0，M-1，meter，&max，&min）；
    /*分治法获取最大值、最小值*/
    print（"\nMax:%d\nMin:%d\n"，max，min）；
    system（"pause"）；
    return0；
    }

又如在教组中查找元素，常用的算法是遍历整个数组进行查找，算法时间复杂度为0（n）；但是对于有序数组，使用二分查找法，可以使时间复杂度减少到O（log2n）  
普通查找法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 2]  
二分法查找法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 3]  
也可以写成递归形式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 4]  
在二分查找法中，通过不断的减少查找区域的范围，把大问题分解成结构相同的小问题，直到问题得解，是分法算法思想的典型体现。  
二分法插入排序：插入排序是经典的简单排序法，它的时间复杂度最坏为0（n2）。代码如下：  
/插入法对数组进行排序，从第二个元素开始，依次把元素插入到其左边比其小的元素之后  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 5]  
再如插入算法，使得当前被插入的元素左侧的数组是已经排蚊子序的。算法思想简单描述：在插入第个元素时，对前面的0-i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，最后把第个元素放在目标位置上。代码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 6]  
包括希尔排序，合并排序和快速排序等排序算法都要用到了分治算法的思想。  
利用分治法解题，在每一层递归上分为以下三个步骤：  
（1）分解：将原问题分解为若干个规模小，相互独立，与原问题形式相同的子问题；  
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题  
（3）合并：将各个子问题的解合并为原问题的解。

## 动态规划法 ##

动态规划法是20世纪50年代由贝尔曼（R.Bellman）等人提出，用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程，就是把研究问题分成若干个相互联系的阶段，由每个阶段都作出决策，从而使整个过程达到最优化。许多实际问题利用动态规划去处理，常比线性规划法更为有效，特别是对于那些离散型问题。实际上，动态规划法就是分多阶段进行决策，其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段，在选定系统行进方向之后，逆着这个行进方向，从终点向始点计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，故又称为逆序决策过程

在这种多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有动态的含义，这种解决多阶段决策最优化问题的方法即动态规划方法。

动态规划是一种在数学和计算机科学中使用的，用于求解包含重雪子问题的最优化问题的方法。其基本思想是将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。  
动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择：而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。用分治法递归求解问题时，每次遇到子问题都会视为新问题，如果存在大量的重叠子问题，会极大地降低算法的效率，而动态规划法总是充分利用重子问题，对每个重叠的子问题仅计算1次，把解保存在一个需要时就可以查询的表中，并使得每次查表的时间为常数，从而提高了算法的执行效率。动态规划法以自底向上的方式计算出最优值，和贪心法一样要求问题具有最优子结构，但不同的是贪心法要求问题具有贪心选择性质，即问题的整体最优解能够通过贪心选择来得到动态规划法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。但是要保证该问题的无后效性，即无论当前取哪个解，对后面的子问题都没有影响。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。

动态规划法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。但是要保证该问题的无后效性即无论当前取哪个解，对后面的子问题都没有影响。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法，动态规划方法并不具有一个标准的数学表达式和明确清晰的解题方法。

动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划，可以解决各类最优化问题。

因此，在学习时除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。  
动态规划的基本模型分为如下5部分：  
（1）确定问题的决策对象；  
（2）对决策过程划分阶段；  
（3）对各阶段确定状态变量；  
（4）根据状态变量确定费用函数和目标函数；  
（5）建立各阶段状态变量的转移过程，确定状态转移方程。

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。最优化原理（最优子结构性质）即一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，-个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。无后效性将各阶段按照一定的次字排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。子问题的重叠性是指动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决元余，这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以，动态规划算法的空间复杂度要大于其它的算法。

动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

作为一个非常有效的算法设计技术，在什么情况下应被采用呢？适合动态规划算法解决的问题往往具有以下两个性质：  
（1）最优子结构。指一个问题的最优解中包含了其子问题的最优解。当一个问题具有最优子结构时，说明动态规划法可能适用。但是，在在这种情形下，贪心法也是有可能适用的。  
（2）重雪子问题。指用来解决原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断调用同一个问题时，就可认为该问题包含重叠子问题。此时采用动态规划法优于分治法递归求解的原因是：分治法每次遇到子问题会视为是新问题，算法的效率被降低了，而动态规划法对于重雪子问题只进行一次，于是可以获得较好的计算效率。

动态规划方法的典型应用场景包括解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等.

如背包问题：解决背包问题的方法有多种，动态规划，贪心算法，回溯法，分支定界法都能解决背包问题。其中动态规划，回溯法，分支定界法都是解决0-1背包问题的方法。背包问题与0-1背包问题的不同点在于在选择物品装入背包时，可以只选择物品的一部分，而不一定是选择物品的全部。在这里，我们组用的有贪心法和动态规划法来对这个问题进行算法的分析设计。用动态规划的方法可以看出如果通过第n次选择得到的是一个最优解的话，那么第n-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。动态规划方法是处理分段过程最优化一类问题极其有效的方法。在该问题中，按照划分阶段、确定状态、进行决策的方法来进行动态规划：

阶段是：在前n件物品中，选取若干件物品放入背包中；  
状态是：在前n件物品中，选取若干件物品放入所剩空间为w的背包中的所最大价值；  
决策是：第1件物品放或者不放；由此可以写出动态转移方程：

![在这里插入图片描述][20210608182028793.png]  
![在这里插入图片描述][20210608181944994.png]

由上述例子可知，利用动态规划算法解题可分为以下两个主要步骤：  
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。  
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]: /images/20210901/74350fedce4440b092873ab915ea7590.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]: /images/20210901/50f1e41534d34ff3966e91a7b1f379b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 2]: /images/20210901/7c17d391bcaf45d583811d6c291472ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 3]: /images/20210901/b5ee751707584419bd5d2d3113eb6d7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 4]: /images/20210901/943a7ec107e1441dbff6491f8b385393.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 5]: /images/20210901/39cc4780461940288802f1d189abdc0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 6]: /images/20210901/26c8e71fa6a3428290dcc53e96d1d56b.png
[20210608182028793.png]: /images/20210901/5e42bebc5f0f491e9c4c7f545d29a60d.png
[20210608181944994.png]: /images/20210901/7d3d848798954d88b0d9cff34b760172.png