动态递推算法

㈠ 递推法的定义是什么

递推法的定义是一种用若干步可重复的简运算规律来描述复杂问题的方法。递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。

其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

递推法的解释

是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。递推联系法是指通过研究递推数列当中相邻的两个或者三个数字之间的递推关系而找到解题关键的方法。

通过一项推出下一项的递推数列为一项递推数列，在利用递推联系法解题时是研究相邻的两个数字之间的关系，俗称圈两数法。通过前两项推出第三项的递推数列为两项递推数列，在利用此法解题时是研究相邻的三个数字之间的关系，俗称圈三数法。

㈡ 动态规划的推法 谢谢

DP是把一个很大的有阶段性有最佳答案问题分割成许多子问题，每个子问题有自己的最优情况（最优子结构），也就是说，每个动态规划的问题都是有许多最有子结构接和起来的，而推法就是要分割出最有子结构
然后对这个小问题得出最优的答案，并由此推出全局的最优解

1.最优子结构性质；

设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾

能量项链其实就是石子合并

算法分析
竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面
的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大）的相邻两堆合并，
形成新的一堆；接下来，在N－1堆中选得分最小（最大）的相邻两堆合并……，依次类推，
直至所有石子经N－1次合并后形成一堆。

例如有6堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为3 46 5
4 2

（图6.2-5）
要求选择一种合并石子的方案，使得做5次合并，得分的总和最小。
按照贪心法，合并的过程如下：
每次合并得分
第一次合并 3 4 6 5 4 2 5
第二次合并 5 4 6 5 4 9
第三次合并 9 6 5 4 9
第四次合并 9 6 9 15
第五次合并 15 9 24
24
总得分＝5＋9＋9＋15＋24＝62

但是当我们仔细琢磨后，可得出另一个合并石子的方案：
每次合并得分
第一次合并 3 4 6 5 4 2 7
第二次合并 7 6 5 4 2 13
第三次合并 13 5 4 2 6
第四次合并 13 5 6 11
第五次合并 13 11 24
24
总得分＝7＋6＋11＋13＋24＝61
显然，后者比贪心法得出的合并方案更优。 题目中的示例故意造成一个贪心法解题的
假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来， 我们先来明确一
个问题：

1．最佳合并过程符合最佳原理
使用贪心法至所以可能出错， 是因为每一次选择得分最小（最大）的相邻两堆合并，
不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果N
－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后
的得分总和必然是最优的。
例如上例中第五次合并石子数分别为13和11的相邻两堆。 这两堆石头分别由最初
的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，
2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2 次合并的得分
总和最优。为了实现这一目标，我们将第1个序列又一分为二：第1、2堆构成子序列1，
第3堆为子序列2。第一次合并子序列1中的两堆，得分7； 第二次再将之与子序列2的
一堆合并，得分13。显然对于第1个子序列来说，这样的合并方案是最优的。同样，我
们将第2个子序列也一分为二；第4堆为子序列1，第5，6堆构成子序列2。第三次合
并子序列2中的2堆，得分6；第四次再将之与子序列1中的一堆合并，得分13。显然
对于第二个子序列来说，这样的合并方案也是最优的。 由此得出一个结论——6堆石子经
过这样的5次合并后，得分的总和最小。
我们把每一次合并划分为阶段，当前阶段中计算出的得分和作为状态， 如何在前一次
合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然，某阶段
的状态给定后，则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性
质符最佳原理，因此可以用动态规划的算法求解。

2．动态规划的方向和初值的设定
采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序
列包括：
｛第1堆、第2堆｝、｛第2堆、第3堆｝、……、｛第N堆、第1堆｝；
｛第1堆、第2堆、第3堆｝、｛第2堆、第3堆、第4堆｝、……、｛第N堆、第1
堆、第2堆｝；
……
｛第1堆、……、第N堆｝｛第1堆、……、第N堆、第1堆｝……｛第N堆、第1堆、
……、第N－1堆｝

为了便于运算，我们用〔i，j〕表示一个从第i堆数起，顺时针数j堆时的子序列
｛第i堆、第i＋1堆、……、第（i＋j－1）mod n堆｝
它的最佳合并方案包括两个信息：
①在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；
②形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的， 因此只需记住
子序列1的堆数；
设
f〔i，j〕——将子序列〔i，j〕中的j堆石子合并成一堆的最佳得分和；
c〔i，j〕——将〔i，j〕一分为二，其中子序列1的堆数；
（1≤i≤N，1≤j≤N）
显然，对每一堆石子来说，它的
f〔i，1〕＝0 c〔i，1〕＝0 （1≤i≤N）
对于子序列〔i，j〕来说，若求最小得分总和，f〔i，j〕的初始值为∞； 若求最大得
分总和，f〔i，j〕的初始值为0。（1≤i≤N，2≤j≤N）。
规划的方向是顺推。先考虑含二堆石子的N个子序列（各子序列分别从第1堆、第2堆、
……、第N堆数起，顺时针数2堆）的合并方案
f〔1，2〕，f〔2，2〕，……，f〔N，2〕
c〔1，2〕，c〔2，2〕，……，c〔N，2〕

然后考虑含三堆石子的N个子序列（各子序列分别从第1堆、第2堆、……、第N堆
数起，顺时针数3堆）的合并方案
f〔1，3〕，f〔2，3〕，……，f〔N，3〕
c〔1，3〕，c〔2，3〕，……，c〔N，3〕
……

依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第1堆、第2堆、 …
…、第N堆数起，顺时针数N堆）的合并方案
f〔1，N〕，f〔2，N〕，……，f〔N，N〕
c〔1，N〕，c〔2，N〕，……，c〔N，N〕

最后，在子序列〔1，N〕，〔2，N〕，……，〔N，N〕中，选择得分总和（f值）最
小（或最大）的一个子序列〔i，N〕（1≤i≤N），由此出发倒推合并过程。

3．动态规划方程和倒推合并过程
对子序列〔i，j〕最后一次合并，其得分为第i堆数起，顺时针数j堆的石子总数t。被
合并的两堆石子是由子序列〔i，k〕和〔（i＋k－1）modn＋1，j－k〕（1≤k≤j－1）
经有限次合并形成的。为了求出最佳合并方案中的k值，我们定义一个动态规划方程：
当求最大得分总和时
f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）

当求最小得分总和时
f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）
其中x＝（i＋k－1）modn＋1，即第i堆数起，顺时针数k＋1堆的堆序号。

例如对（图6．2－4）中的6堆石子，按动态规划方程顺推最小得分和。 依次得出含
二堆石子的6个子序列的合并方案
f〔1，2〕＝7 f〔2，2〕＝10 f〔3 ，2〕＝11
c〔1，2〕＝1 c〔2，2〕＝1 c〔3，2〕＝1
f〔4，2〕＝9 f〔5，2〕＝6 f〔6，2〕＝5
c〔4，2〕＝1 c〔5， 2〕＝1 c〔6，2〕＝1

含三堆石子的6个子序列的合并方案
f〔1，3〕＝20 f〔2，3〕＝25 f〔3，3〕＝24
c〔1，3〕＝2 c〔2，3〕＝2 c〔3，3〕＝1
f〔4，3〕＝17 f〔5，3〕＝14 f〔6，3〕＝14
c〔4，3〕＝1 c〔5，3〕＝1 c〔6，3〕＝2

含四堆石子的6个子序列的合并方案
f〔1，4〕＝36 f〔2，4〕＝38 f〔3，4〕＝34
c〔1，4〕＝2 c〔2，4〕＝2 c〔3，4〕＝1
f〔4，4〕＝28 f〔5，4〕＝26 f〔6，4〕＝29
c〔4，4〕＝1 c〔5，4〕＝2 c〔6，4〕＝3

含五堆石子的6个子序列的合并方案
f〔1，5〕＝51 f〔2，5〕＝48 f〔3，5〕＝45
c〔1，5〕＝3 c〔2，5〕＝2 c〔3，5〕＝2
f〔4，5〕＝41 f〔5，5〕＝43 f〔6，5〕＝45
c〔4，5〕＝2 c〔5，5〕＝3 c〔6，5〕＝3

含六堆石子的6个子序列的合并方案
f〔1，6〕＝61 f〔2，6〕＝62 f〔3，6〕＝61
c〔1，6〕＝3 c〔2，6〕＝2 c〔3，6〕＝2
f〔4，6〕＝61 f〔5，6〕＝61 f〔6，6〕＝62
c〔4，6〕＝3 c〔5，6〕＝4 c〔6，6〕＝3

f〔1，6〕是f〔1，6〕，f〔2，6〕，……f〔6，6〕中的最小值，表明最小
得分和是由序列〔1，6〕经5次合并得出的。我们从这个序列出发， 按下述方法倒推合
并过程：
由c〔1，6〕＝3可知，第5次合并的两堆石子分别由子序列〔1，3〕和子序列〔
4，3〕经4次合并后得出。其中
c〔1，3〕＝2可知由子序列〔1，3〕合并成的一堆石子是由子序列〔1，2〕和
第三堆合并而来的。而c〔1，2〕＝1，以表明了子序列〔1，2〕的合并方案是第1堆
合并第2堆。
由此倒推回去，得出第1，第2次合并的方案
每次合并得分
第一次合并 3 4 6…… 7
第二次合并 7 6…… 13
13……
子序列〔1，3〕经2次合并后合并成1堆， 2次合并的得分和＝7＋13＝20。
c〔4，3〕＝1，可知由子序列〔4，3〕合并成的一堆石子是由第4堆和子序列〔5，
2〕合并而来的。而c〔5，2〕＝1，又表明了子序列〔5，2〕的合并方案是第5堆合
并第6堆。由此倒推回去，得出第3、第4次合并的方案
每次合并得分
第三次合并 ……54 2 6
第四次合并 ……5 6 11
……11
子序列〔4，3〕经2次合并后合并成1堆，2次合并的得分和＝6＋11＝17。
第五次合并是将最后两堆合并成1堆，该次合并的得分为24。
显然，上述5次合并的得分总和为最小
20＋17＋24＝61

上述倒推过程，可由一个print（〔子序列〕）的递归算法描述
procere print （〔i，j〕）
begin
if j〈〉1 then ｛继续倒推合并过程
begin
print（〔i，c〔i，j〕）；｛倒推子序列1的合并过程｝
print（〔i＋c〔i，j〕－1）mod n＋1，j－c〔i，j〕）
｛倒推子序列2的合并过程｝
for K：＝1 to N do｛输出当前被合并的两堆石子｝
if （第K堆石子未从圈内去除）
then begin
if（K＝i）or（K＝X）then置第K堆石子待合并标志
else第K堆石子未被合并；
end；｛then｝
第i堆石子数←第i堆石子数＋第X堆石子数；
将第X堆石子从圈内去除；
end；｛then｝
end；｛print｝
例如，调用print（〔1，6〕）后的结果如下：
print（〔1，6〕）⑤
│
┌——————┴——————┐
│ │
print（〔1，3〕）② print（〔4，3〕）④
│ │
print（〔1，2〕）① ┌—————┴—————┐
│ │ │
│
┌—————┴—————┐ print（〔4，1〕） print（〔5，2〕）③
│ │ │
print（〔1，1〕） print（〔2，1〕） │
┌——————┴——————┐
│ │
print（〔5，1〕） print（〔6，1〕）
（图6.2-5）
其中回溯至
① 显示 3 46 5 4
② 显示 7 65 4 2
③ 显示 13 54 2
④ 显示 135 6
⑤ 显示 13 11
注:调用print过程后，应显示6堆石子的总数作为第5次合并的得分

㈢ 递推算法是怎么回事

递推定义
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递推算法分为顺推和逆推两种。

顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

逆推法
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

递推与递归的比较
相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.

比如阶乘函数：f(n)=n*f(n-1)

在f(3)的运算过程中,递归的数据流动过程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而递推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意.

㈣ 递推估计算法的概述

递推估计算法recursive estimation algorithm
利用时刻t上的参数估计、存储向量与时刻 t+1上测量的输入和输出值u(t+1)和y(t+1)计算新参数值(t+1),再根据(t+1)计算出新参数值(t+2)，直到获得满意的参数值为止。这种算法的每一步计算量都比较小，能够使用小型计算机进行离线或在线参数估计，可以估计时变参数，也可以实时估计适应控制器的参数（见适应控制系统）。20世纪60年代，递推估计算法得到迅速发展，到了70年代产生了许多不同的方法，例如，有离线方法的各种变形、卡尔曼滤波法、随机逼近方法和模型参考适应参数递推估计法等。
递推估计算法的各种方法可以用一个统一的公式来描述：