简单基础动态规划（递推+各种背包）

题解 动态规划 斐波那契
Markdown
发布日期:   2021-09-09
更新日期:   2021-10-09
文章字数:   4.9k
阅读次数:  

动态规划考题灵活，但是只要找到状态转移方程，就可以解决这道题。首先要有找到枚举状态的能力。

递推

例1：数塔

            9
           / \
          /   \
        12     15
        / \   / \
       /   \ /   \
     10     6     8
     / \   / \   / \
    /   \ /   \ /   \
   2    18     9     5
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
19    7    10     4     16

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

输入格式

输入数据首先包括一个整数 $C$,表示测试实例的个数，每个测试实例的第一行是一个整数 $N$，表示数塔的高度，接下来用N行数字表示数塔，其中第 $i$ 行有个 $i$ 个整数。

输出格式

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

样例输入

1
5
 9
12 15
10  6  8
 2 18  9  5
19  7 10  4 16

样例输出

59

数据范围

$1$ $<=$ $N$ $<=$ $100$，所有的整数均在区间 $[0,99]$ 内。

题解

从底层开始，不断向上遍历，每个节点保留从下面传上来的最大值加上它的本身价值，传到根节点即可（递推的过程）。

            9
           / \
          /   \
        12     15
        / \   / \
       /   \ /   \
     10     6     8
     / \   / \   / \
    /   \ /   \ /   \
   2    18     9     5
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
19    7    10     4     16

从底层向上遍历，更新节点价值。例如：$19$ （左下角）更新 $2$ 的权值，$2$ 变成 $21$。$7$ 也可能要更新 $2$ 的权值，但由于没有 $19$ 更新过后的数值大，所以更新失败。

          9
         / \
        /   \
      12     15
      / \   / \
     /   \ /   \
   10     6     8
   / \   / \   / \
  /   \ /   \ /   \
21    28     19    21

第一次更新后的结果。然后递推处理，最后输出根节点的值即可。（下面是每一步的更新过程）

       9
      / \
     /   \
   12     15
   / \   / \
  /   \ /   \
38    34    29
    9
   / \
  /   \
50     49
59

例2：兔子数列（斐波那契）

直接看 斐波那契 吧，太经典了。

斐波那契数列的的形成就是通过前两项递推的，本身也是动态转移的思想。

例3：Working out

CF429B Working out

根据题目，我们不难发现两人一人要从左下角到右上角，一人从左上角，到右下角，且中间会有一次相遇。

关键在于那一次相遇的地点选择，并且从相遇点到终点和终点跑到相遇点的性质其实相同。所以我们可以考虑，四个人从四个角跑到一个点，左上角的人只能向右或向下；左下角的人只能向右或向上；右上角的人只能向左后向下；右下角的人只能向左或向上。四人跑到这个点路径的权值和最大。

由于我们不知道相遇的地方在哪，所以我们可以通过枚举相遇的点来比对找到最终的最大值。

那么如何使起点到这个点路径的权值和最大呢？

通过递推，找出起点到全图上所有点的权值都最大。已左上角举例。

for(int i=1;i<=n;i++)//左上角递推 
    for(int j=1;j<=m;j++)
    	z_s[i][j]=a[i][j]+max(z_s[i-1][j],z_s[i][j-1]);

但是，我们可以发现每个角到一点回合时，进入点的方向也可能不同。分为两种情况（由于方向约束）。

      左上角
左下角 汇合 右上角
      右下角

      右上角
左上角 汇合 右下角
      左下角
  • 在计算结果的时候要判一下两种结果最大值。
  • 我们的讨论的点上下左右四个都可以达到，所以这个相遇的点不在边线上。
  • “另外，他们的健身速度不同，所以可以走过的路线长度也不同。”所以，我们不用特判他 们的速度是否合法。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const long long o_o=1e3+10;
using namespace std;
long long z_s[o_o][o_o];//左上角
long long y_x[o_o][o_o];//右下角
long long z_x[o_o][o_o];//左下角
long long y_s[o_o][o_o];//右上角
int x,y;
int a[o_o][o_o];
int main(){
    x=r_r(),y=r_r();
    for(int i=1;i<=x;i++)//读入 
        for(int j=1;j<=y;j++)a[i][j]=r_r();
    for(int i=1;i<=x;i++)//左上角递推 
        for(int j=1;j<=y;j++)
        	z_s[i][j]=a[i][j]+max(z_s[i-1][j],z_s[i][j-1]);
    for(int i=x;i>=1;i--)//右下角递推 
        for(int j=y;j>=1;j--)
        	y_x[i][j]=a[i][j]+max(y_x[i+1][j],y_x[i][j+1]);
    for(int i=x;i>=1;i--)//左下角递推 
        for(int j=1;j<=y;j++)
        	z_x[i][j]=a[i][j]+max(z_x[i+1][j],z_x[i][j-1]);
    for(int i=1;i<=x;i++)//右上角递推 
        for(int j=y;j>=1;j--)
        	y_s[i][j]=a[i][j]+max(y_s[i-1][j],y_s[i][j+1]);
    long long m_a=0;
    for(int i=2;i<x;i++)//找最大值 
        for(int j=2;j<y;j++)
        	m_a=max(max(m_a,z_s[i][j-1]+y_x[i][j+1]+z_x[i+1][j]+y_s[i-1][j]),max(m_a,z_s[i-1][j]+y_x[i+1][j]+z_x[i][j-1]+y_s[i][j+1]));        
    printf("%lld\n",m_a);
    return 0;
}

01背包

接下来的 $3$ 道题，非常经典！

例4：采药

P1048 NOIP2005 普及组 采药

一句话题意：限时间，价值最大化，药有限。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
int d_p[1001][1001];
int main(){
    int m_t=r_r(),n_x=r_r();//总时间，药个数 
	for(int i=1;i<=n_x;i++){//每次有新药，更新一次 
		int t_i=r_r(),v_i=r_r();//这个药花费的时间，价值 
        for(int j=m_t;j>=0;j--){//枚举剩下的时间 
            d_p[i][j]=(i==1?0:d_p[i-1][j]);//继承上一个状态 
            if(j>=t_i)d_p[i][j]=max(d_p[i][j],d_p[i-1][j-t_i]+v_i);//如果时间够用，更新状态 
        }
	}
	printf("%d",d_p[n_x][m_t]);//最新状态，在时间内的答案 
	return 0;
}

例5：装箱

P1049 NOIP2001 普及组 装箱问题

一句话题意：限空间，占用空间最大化，物品有限。

这道题用一维数组写（滚动数组）（时间换空间）

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long r_r(){
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=2e4+10;
int v_i[o_o];//物品体积 
int d_p[o_o];
int main(){
	int m_v=r_r(),n_x=r_r();//箱子大小，物品数量 
	for(int i=1;i<=n_x;i++)v_i[i]=r_r();//存入物品体积 
	for(int i=1;i<=n_x;i++)//每个物品来的时候更新状态 
		for(int j=m_v;j>=v_i[i];j--)//有这个物品的空间 
			d_p[j]=max(d_p[j-v_i[i]]+v_i[i],d_p[j]);//占的地方尽量大 
	printf("%d\n",m_v-d_p[m_v]);//输出浪费的最小空间 
	return 0;
}

动态规划：现在决定未来，未来与过去无关。

所以采药为例，每回返回上一个状态后，上一个状态就没用了，极大浪费空间。可以改进为如下代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long r_r(){
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e3+10;
struct po{
	int t;//使用时间 
	int v;//获得价值 
}x_i[o_o];
int d_p[o_o];
int main(){
	int m_t=r_r(),a_x=r_r();
	for(int i=1;i<=a_x;i++)x_i[i].t=r_r(),x_i[i].v=r_r();//读入基础信息 
	for(int i=1;i<=a_x;i++)//每个药都要更新结果 
		for(int j=m_t;j>=x_i[i].t;j--)//有时间采这个药 
			d_p[j]=max(d_p[j],d_p[j-x_i[i].t]+x_i[i].v);//更新结果 
	printf("%d",d_p[m_t]);
	return 0;
}

例6：烹调方案

P1417 烹调方案

假如相邻的两个物品 $x$，$y$ 。假设现在已经耗费 $t$ 的时间，那么分别列出先做 $x$，$y$ 的代价：

  • $1$ 式：$a[x]-(t+c[x])\times b[x]+a[y]-(t+c[x]+c[y])\times b[y] $

  • $2$ 式：$a[y]-(t+c[y])\times b[y]+a[x]-(t+c[y]+c[x])\times b[x] $

不难看出时间（做菜顺序）对结果是有影响的，所以要将价值最大化，就要按一定顺序排好后，再跑 $01$ 背包，所以我们要将 $1$ 式和 $2$ 式做出比对以确定顺序。

当 $c[x]\times b[y] < c[y]\times b[x]$ 时，$1$ 式 $>$ $2$ 式。我们就可以根据这个性质来排序。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=100001; 
struct po{
	long long a;
	long long b;
	long long c;
}x_i[o_o];
long long d_p[o_o<<2];
bool cmp(po a,po b){//最优排序 
	return a.c*b.b<a.b*b.c;
}
int main(){
    int m_t=r_r(),x_n=r_r();//最大时间，菜的个数 
    for(int i=1;i<=x_n;i++)x_i[i].a=r_r();
    for(int i=1;i<=x_n;i++)x_i[i].b=r_r();
    for(int i=1;i<=x_n;i++)x_i[i].c=r_r();
    sort(x_i+1,x_i+1+x_n,cmp);//最优排序 
    for(int i=1;i<=x_n;i++)//枚举每道菜 
    	for(int j=m_t;j>=x_i[i].c;j--)//有时间做 
    		d_p[j]=max(d_p[j],d_p[j-x_i[i].c]+x_i[i].a-j*x_i[i].b);//根据题意算最大值
			//注意，这里的 j 就是题目中的 t 时刻 
    long long a_s=0;
    for(int i=1;i<=m_t;i++)a_s=max(a_s,d_p[i]);//找最大值，有可能菜会更新出负数的美味值，影响最终结果 
	printf("%lld",a_s); 
	return 0;
}

完全背包

例7：疯狂的采药

P1616 疯狂的采药

一句话题意：限时间，价值最大化，药无限。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long r_r(){
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e4+10,m_a=1e7+10;
struct po{
	int t;//这种药的时间 
	int v;//这种药的价值 
}x_i[o_o];
long long d_p[m_a];
int main(){
	long long m_t=r_r(),n_x=r_r();//读入时限，药的种类 
	for(int i=1;i<=n_x;i++)x_i[i].t=r_r(),x_i[i].v=r_r();//每个种类的药的时间和价值 
	for(int i=1;i<=n_x;i++)//每选一种药更新 
		for(int j=x_i[i].t;j<=m_t;j++)//有时间采这个药 
			d_p[j]=max(d_p[j],d_p[j-x_i[i].t]+x_i[i].v);//更新 
	printf("%lld",d_p[m_t]);//输出这个时间最多获得的价值 
	return 0;
}

对比

在药有限时：

for(int j=m_t;j>=x_i[i].t;j--)
	d_p[j]=max(d_p[j],d_p[j-x_i[i].t]+x_i[i].v);

在药无限时：

for(int j=x_i[i].t;j<=m_t;j++) 
	d_p[j]=max(d_p[j],d_p[j-x_i[i].t]+x_i[i].v);

不难发现，只是循环顺序有变，但是性质完全不同。但是很好理解，因为我们现在将二维数组压缩成一位数组了。

我们倒着遍历的原因是什么（采药）？

为的是这个结果不会干扰别的状态。所以从后向前遍历，这样每回后面的状态根据前面的变化，但是前面的值在遍历前不会改变，所以后面的状态要重复借助前面的状态时不会受到影响。

那影响会发生什么（即从前往后遍历）？

就是药无限的情况。因为在前面的时候假如已经选了一次这个药，后面的遍历的时候状态都是建立在已经选了一次这个药的基础上，所以可能再选这个药很多次。

多重背包

英雄联盟

P5365 SNOI2017 英雄联盟

与 $01$ 背包不同的是此类题的物品不再只是 $1$ 个，所以可直观的理解为多了一层枚举每个物品选几个的循环。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1000001; 
long long d_p[o_o];//下标是用的钱数，值为多少种策略 
struct po{
	int k;//皮肤数量 
	int c;//皮肤价格 
}x_i[o_o]; 
long long s_m;//需要钱的总数 
int main(){
	long long n=r_r(),m=r_r();
	for(int i=1;i<=n;i++)x_i[i].k=r_r();//读入皮肤数量 
	for(int i=1;i<=n;i++){
		x_i[i].c=r_r();//皮肤价格 
		s_m+=x_i[i].c*x_i[i].k;//所有皮肤买下需要的钱 
	}
	d_p[0]=1;//后面的处理涉及到乘法，所以要初始化 
	for(int i=1;i<=n;i++)//每个新的英雄出现都要更新 
		for(int j=s_m;j>=0;j--)//有钱买皮肤 
			for(int p=0;p<=x_i[i].k&&p*x_i[i].c<=j;p++)//不能超过现有（枚举）的钱，枚举的次数不能超过皮肤总数 
				d_p[j]=max(d_p[j],d_p[j-p*x_i[i].c]*p);//更新答案 
	long long a_s=0;
	while(a_s<=s_m&&d_p[a_s]<m)a_s++;//找到满足要求的就退出，而枚举的钱是从小到大，所以最优 
	printf("%lld",a_s);
	return 0;
}

宝物筛选（二进制优化）

P1776 宝物筛选

因为二进制可以覆盖所有的数，所以讲一个数也可以分成二进制而不破坏其完整性。

例如： $11=1+2+4+4$

而这 $4$ 个分出来的数可以表示 $[1,11]$ 之间的所有书。所以可以将物品的数量分解成几个部分，但不影响取的数量的可能性。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;
int a_s,x_p=1;
int d_p[o_o];//下标存分的部分，值存价值 
struct po{
	int w;//重量 
	int v;//价值 
}x_i[o_o];
int main(){
    int n_x=r_r(),m_w=r_r();//宝物有几种，最大载重 
    for(int i=1;i<=n_x;i++){
        int v_i=r_r(),w_i=r_r(),m_i=r_r();//读入每种宝物的基本信息 
        for(int j=1;j<=m_i;j<<=1){//将数量分开存 
        	x_p++;
            x_i[x_p].v=j*v_i;//分成这部分的总价值 
			x_i[x_p].w=j*w_i;//分成这部分的中重量 
            m_i-=j;//分出去的减去 
        }
        if(m_i)x_p++,x_i[x_p].v=v_i*m_i,x_i[x_p].w=w_i*m_i;//还剩下的不够整分，单独存 
    }
    for(int i=1;i<=x_p;i++)//枚举存的单位 
     	for(int j=m_w;j>=x_i[i].w;j--)//还能承重 
      		d_p[j]=max(d_p[j],d_p[j-x_i[i].w]+x_i[i].v);//更新结果 
    printf("%d\n",d_p[m_w]);//输出 
    return 0;
}

多重背包+完全背包

The Fewest Coins G

P2851 USACO06DEC The Fewest Coins G

不难得出，我们要找到买物品花的硬币数加找钱的硬币数的总和最小。我们可以枚举真正花的钱（大于目标价），买家跑多重背包（钱币有限），卖家跑完全背包（钱币无限）加和取最小。

枚举的最大范围是最大钱币的平方加目标价的和，因为如果能拿最大钱币的最大钱币的面值个那么一定不是最优。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;
int f[o_o],g[o_o];
struct po{
	int v;//钱币价值 
	int c;//钱币个数 
}x_i[o_o];
int main(){
    int n=r_r(),t=r_r();
    for(int i=1;i<=n;i++)x_i[i].v=r_r();
    int s_m=0,m_x=0;
    for(int i=1;i<=n;i++){
        x_i[i].c=r_r();
        s_m+=x_i[i].c*x_i[i].v;//计算买家所有钱的和 
        m_x=max(m_x,x_i[i].v*x_i[i].v);//找钱最大范围 
    }
    if(s_m<t){//买的人所有钱加起来都买不起 
        printf("-1\n");
        return 0;
    }
    memset(g,0x3f,sizeof(g));
    memset(f,0x3f,sizeof(f));
    g[0]=0;f[0]=0;
	//卖家完全背包 
    for(int i=1;i<=n;i++)//每种钱币更新 
        for(int j=x_i[i].v;j<=m_x;j++)//还有“挥霍”空间 
            g[j]=min(g[j],g[j-x_i[i].v]+1);//前面对后面有影响，能少张数就少 
    //买家多重背包 
	for(int i=1;i<=n;i++){//每种钱币更新 
        for(int j=1;j<=x_i[i].c;j<<=1){//二分优化多重背包，变为 01 背包 
            for(int k=t+m_x;k>=j*x_i[i].v;k--)//还有“挥霍”空间 
                f[k]=min(f[k],f[k-j*x_i[i].v]+j);//能少给张数就少给 
            x_i[i].c-=j;//分出去的钱减去 
        }
        if(x_i[i].c)//有剩余张数 
            for(int k=t+m_x;k>=x_i[i].c*x_i[i].v;k--)//剩下的单独分成一块 
                f[k]=min(f[k],f[k-x_i[i].c*x_i[i].v]+x_i[i].c);//直接比较 
    }
    int a_s=0x3f3f3f3f;
    for(int i=t;i<=t+m_x;i++)a_s=min(a_s,f[i]+g[i-t]);//找到用的最少的张数 
    if(a_s==0x3f3f3f3f)puts("-1");//没找到 
	else printf("%d\n",a_s);
    return 0;
}

有依赖的背包

金明的预算方案

P1064 NOIP2006 提高组 金明的预算方案

找好主附件之间的联系后跑 $01$ 背包即可。由于配件数量过少，情况特判即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e6+10;
int n,m;
int v,p,q;
int z_w[o_o],z_c[o_o]; 
int f_w[o_o][3],f_c[o_o][3];//一个主件最多两个附件 
int f[o_o];
int main(){
    n=r_r(),m=r_r();
    for(int i=1;i<=m;i++){
        v=r_r(),p=r_r(),q=r_r();
        if(!q){
            z_w[i]=v;//主件价格 
            z_c[i]=v*p;//价格*重要度（结果要使这个最大） 
        }
        else{
            f_w[q][0]++;//它属于的主件的附件数量增加（下标） 
            f_w[q][f_w[q][0]]=v;//存入价格 
            f_c[q][f_w[q][0]]=v*p;//价格*重要度 
        }
    }
    for(int i=1;i<=m;i++)//有 m 种物品，每多一种，更新一次 
        for(int j=n;z_w[i]!=0&&j>=z_w[i];j--){//只用枚举主件即可（附件很少暴力即可） 
            f[j]=max(f[j],f[j-z_w[i]]+z_c[i]);//是否比买了它的主件更优 
            if(j>=z_w[i]+f_w[i][1])//是否比买了它的第一个附件更优 
                f[j]=max(f[j],f[j-z_w[i]-f_w[i][1]]+z_c[i]+f_c[i][1]);
            if(j>=z_w[i]+f_w[i][2])//是否比买了它的第二个附件更优 
                f[j]=max(f[j],f[j-z_w[i]-f_w[i][2]]+z_c[i]+f_c[i][2]);
            if(j>=z_w[i]+f_w[i][1]+f_w[i][2])//是否比两个附件都买更优 
                f[j]=max(f[j],f[j-z_w[i]-f_w[i][1]-f_w[i][2]]+z_c[i]+f_c[i][1]+f_c[i][2]);
            //最多有 2 种附件，所以只用枚举 4 种情况，若没有附件不会影响结果（+0 不会更新结果） 
    	}
	printf("%lld\n",f[n]);//输出结果 
    return 0;
}
文章作者: 王大神——A001
文章链接: http://wdsa001.github.io/2021/09/09/jian-dan-ji-chu-dong-tai-gui-hua-di-tui-ge-chong-bei-bao/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 王大神——A001 !
题解 动态规划 斐波那契
  目录