算法--递推策略

引例：Fibonacci数列 

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。

问题：

一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。 

 f[0]:=0; f[1]:=1;

 for i:=2 to n do f[i]:=f[i–1]+f[i–2];

总结:

从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。

对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。

递推概念

• 如何建立递推关系

• 递推关系有何性质

• 如何求解递推关系

解决递推问题的一般步骤

• 建立递推关系式

• 确定边界条件

• 递推求解

递推的两种形式

顺推法和倒推法

递推的应用分类

• 一般递推问题

• 组合计数类问题

• 一类博弈问题的求解

• 动态规划问题的递推关系

（一）递推的应用（一般递推问题）

#include <iostream>
using namespace std;
int a[31][31];
int main( )
{
    int i,j,n;
    a[0][0]=a[1][0]=a[1][1]=1;
    for(i=2; i<31; i++) {
        for(j=0; j<=i; j++) {
            if(j==0 || i==j) {
                a[i][j]=1;
            } else {
                a[i][j]=a[i-1][j-1]+a[i-1][j];
            }
        }
    }
    while(cin>>n) {
        for(i=0; i<n; i++) {
            for(j=0; j<=i; j++) {
                if(j!=0) cout<<" ";
                cout<<a[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    } 
    return 0;
}

 

当n=1时：A->C

当n=2时：A->B,A->C,B->C

当n=3时：

 

例题4：数的计数

【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n)，先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：
1.不作任何处理；
2.在它的左边加上一个自然数，但该自然数不能超过原数的一半；
3.加上数后，继续按此规则进行处理，直到不能再而 自然数为止；

 方法1：用递推

用h[n]表示自然数n所能扩展的数据个数，则：h[1]=1,h[2]=2,h[3]=2,h[4]=4,h[5]=4,h[6]=6,h[7]=6,h[8]=10,h[9]=10。分析上数据，可得递推公式：h[i]=1+h[1]+h[2]+…+h[i/2]。时间复杂度O(n²)。 

     s(x)=h(1)+h(2)+…+h(x),

     h(x)=s(x)-s(x-1)

    此算法的时间复杂度可降到O(n)。

方法3：还是用递推

只要做仔细分析，其实我们还可以得到以下的递推公式：

(1)当i为奇数时,h(i)=h(i-1);

(2) 当i为偶数时,h(i)=h(i-1)+h(i/2);

【例题6】传球游戏

分析：

设f[i][k]表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式：

f[i][k]=f[i-1][k-1]+f[i+1][k-1]

f[1][k]=f[n][k-1]+f[2][k-1],   当i=1时

f[n][k]=f[n-1][k-1]+f[1][k-1],   当i=1时

边界条件：f[1][0]=1；结果在f[1][m]中。

核心代码：

cin>>n>>m;
memset(f,0,sizeof(f));
f[1][0]=1;
for(k=1;k<=m;k++)
{   
    f[1][k]=f[2][k-1]+f[n][k-1];
    for(i=2;i<=n-1;i++)f[i][k]=f[i-1][k-1]+f[i+1][k-1];
    f[n][k]=f[n-1][k-1]+f[1][k-1];
}
cout<<f[1][m]<<endl;

（三）递推的应用（组合计数）

Catalan数

如图，有一个正n+2边形。任取一边，从这边的端点开始，依次顺时针给顶点编号为：0,1,2,3,….,n,n+1(所取的边端点编号为:0,n+1)。这样，除线段所在顶点外，还有n个顶点：1,2,3,…,n。我们以该线段为三角形的一条边，另一个顶点为i(1<=i<=n)。 

具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式:

再进行递推计算，并且注意类型的定义要用long long长整型。

（四）递推的应用（博弈问题）

例题：走直线棋问题。

有如下所示的一个编号为1到n的方格：

现由计算机和人进行人机对奕，从1到n，每次可以走k个方格，其中k为集s={a₁,a₂, a₃,....a_m}中的元素(m<=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。

分析:

题设条件：若谁先走到第N格谁将获胜，例如，假设S={1,2}，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。

设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。

例如，设N＝10，S＝{1,2}，则可确定其每个棋格的状态如下所示：

而N＝10，S＝{2,3}时，其每格的状态将会如下所示：

有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，就能保证计算机尽可能不败。

（五）递推的应用（动态规划中的递推）

例题：方格取数

在一个n×m的方格中，m为奇数，放置有n×m个数 ，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。

分析:

我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下：

F_x,y= Max{F_x+2,y-1 ,F_x+1,y-1,F_x,y-1,F_x-1,y-1,F_x-2,y-1}+Num_x,y，

其中Num_x,y 表示(x,y) 点上的数字。

边界条件为：

动态规划与递推的关系

上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢？

我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。

1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视

2、一般递推数学性较强,动态规划数学性相对较弱

3、一般递推一般不划分阶段,动态规划一般有较为明显的阶段

PS：更多递推练习，可以看看《递推求解专题练习》