递推算法！（鸣谢@SXY大佬教我真正的递推算法，用魔法打败魔法，谢谢神犇！！！）

递推
递推是经常被使用的一种简单的算法。递推是一种用若干步可重复的简单运算来描述复杂问题的方法。

递推的特点在于，每一项都和他前面的若干项由一定的关联，这种关联一般可以通过递推关系式来表示，可以通过其前面若干项得出某项的数据。

对于递推问题的求解一般从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得出想要的结果，这种求解问题的方法叫递推法。其中，初始的若干数据项称为边界。
————————————————
原文链接：https://blog.csdn.net/Richard__Ting/article/details/79679648

上文是对递推的基本定义是扒的CSDN大佬的文章，附上原文链接，致敬神犇！！！

递推是一种经常用到的简单算法，但是我这种蒟蒻上课的时候莫有听懂！！

但是还要刷题打卡，这可咋整？

当然是走歪门邪道了！！

ybt 1189

【题目描述】

Pell数列a1,a2,a3,...">a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2)">a1=1,a2=2,...,an=2*an?1+an?2(n>2)

给出一个正整数k，要求Pell数列的第k项模上32767是多少。

【输入】

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。

【输出】

n行，每行输出对应一个输入。输出应是一个非负整数。

这是我刷的第一个递推题，题目要求求出PELL数列的第K项对32767的模。

给出的K范围非常大。K的值在一百万以内，不仅爆时间，数据范围也会爆。

我又不会递推……

尝试一下歪门邪道……

上本蒟蒻代码（小声BB）

//1202
#include
using namespace std;
int jiyihua[1000000];
int a;
int Pell(int x)
{
    if (jiyihua[x]!=0) 
    {
        return jiyihua[x];
    }
    if (x==1)
    {
        return 1;//递归边界
    }
    if (x==2)
    {
        return 2;
    }
    return jiyihua[x]=(2*Pell(x-1)%32767+Pell(x-2)%32767)%32767;
}
int main()
{
    int n;
    cin>>n;
    for (int i=0;i)
    {
        cin>>a;
        cout<endl;
    }
    return 0;
}

记忆化是歪门邪道，下面才是正规做法。

emmmm……反正先AC了再说(逃

上递推代码

//1189递推
#include
using namespace std;
int Pell[1000000];
int main()
{
    int n,num;
    cin>>n;
    Pell[1]=1;
    Pell[2]=2;//初始化递推数组
    for (int i=0;i)
    {
        cin>>num;
        for (int j=3;j<=num;j++)
        {
            Pell[j]=(Pell[j-1]*2%32767+Pell[j-2]%32767)%32767; //递推式加每步取模，不爆int
        }
        cout<endl;
    }
    return 0;
} 

这是正规军。。。

好了抬走下一位！！！

ybt1188

嗯！又是大家喜闻乐见的斐波那契时间！！！

先上题目!

【题目描述】

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。

【输入】

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 ≤ a ≤ 1000000)。

【输出】

n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。

需要注意的是，这次斐波那契不是单纯的递归了，出题人把他重新包装了一遍，难度提升了，简直是诚意满满（丧心病狂）！

可以看到，题目中给的a的值也是一百万。这样的话递归也是会爆的（如果我没记错的话递归斐波那契45次就要220000ms以上的时间了，肯定超时）

那么还是选择愉快的递推，递推式很好想，就是题目中给出的斐波那契公式，即 f(n)=f(n-1)+f(n-2)   (n>=3)

递推式有了，程序就好写了（小声BB）

上本蒟蒻代码

//1188
#include
using namespace std;
int fei[1000001];//大同小异，先定义递推数组，大小等于n+1
int main()
{
    int n;
    cin>>n;
    fei[1]=1;//初始化递推数组
    fei[2]=1;
    for (int i=0;i)
    {
        int num;
        cin>>num;for (int j=3;j<=num;j++)
        {
             fei[j]=(fei[j-1]+fei[j-2])%1000;//开始递推,别忘了取模!!!
        }
        cout<endl;//输出答案
    }
    return 0;
}

行了这两个题其实都挺水的，我不BB大家也都能一次就AC。但是我要写递推的博客，所以先水一下博文长度。

我个人才疏学浅，是个不折不扣的蒟蒻，递推的方法我也就用到了这两个题里而已。。。

下面是用物理硬核打败魔法时间。。（正文部分）

ybt1193

先上题目！

【题目描述】

名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力，0

【输入】

输入只有1行，即整数N。

【输出】

输出只有1行，即名名吃巧克力的方案数。

emmm，这个题，明眼人都看出来是一个斐波那契数列。。。

但是我个人菜鸡，莫有看出来，所以。。

我选择了爆搜。。。先上代码。

//1193
#include
using namespace std;
int way;
void dfs(int x,int y)
{
    if (x>y)//不能吃的糖比总数还多，不然搜索不能结束，会GG
    {
        return;
    }
    if (x==y)
    {
        way++;//如果搜到一种情况，吃的糖和买的糖一样多，视为一种方法，答案++
        return;
    }
    dfs(x+1,y);//爆搜时间到！！！
    dfs(x+2,y);
}
int main()
{
    int n;
    cin>>n;
    dfs(0,n);//一开始没吃糖，所以是0
    cout<<way;
    return 0;
}

emmm，出题人比较良心，没有卡我的爆搜。

递推正规方法是把上面的斐波那契程序改成输出n+1项就好了，不多做BB。

抬走下一位。。。

ybt1190

【题目描述】

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

【输入】

输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

【输出】

每一行输出对应一行输入的结果，即为走法的数目。

先说递推/归策略！

我们假设要上到第n级台阶。

那么我们可以从第n-3级上3级到第n级，

或者从第n-2级上2级到第n级，

再或者从第n-1级上1级到第n级。

没有别的情况了。。。

所以我们上到第n级台阶的方法有3种，一种是上到n-3级，一种是上到n-2级，还有一种是上到n-1级。

而n-3，n-2，n-1的方法数也是由此可以得出的。

所以，递推/归式就很明显了。

f（n）=f（n-1）+f（n-2）+f（n-3）   （n>3）

我个人这两种方法都没用。。。（因为当时没想这么多，直接搜索的）

上搜索代码。一开始我是用的爆搜，但是出题人学坏了，爆搜被TLE卡死。所以改了一下，改成了记忆化，顺利AC。

//1190
#include
using namespace std;
long long mapp[200];//开记忆化数组
long long f(long long step)
{
    if (step==1)
    {
        return 1;//设置递归边界
    }
    if (step==2)
    {
        return 2;
    }
    if (step==3)
    {
        return 4;
    }
    if (mapp[step-2]!=0&&mapp[step-3]!=0&&mapp[step-1]!=0)
    {
        return mapp[step-2]+mapp[step-3]+mapp[step-1];//如果已经被搜过了，就调用记忆化的结果
    }
    return mapp[step]=f(step-1)+f(step-2)+f(step-3);//如果没有被搜过，记忆结果
}
int main()
{
    long long n;//因为是到71，所以结果可能非常大，要用long long才能存，一开始我用的int 各种被爆掉，错了好几遍才幡然醒悟
    for (;;)//用死循环for输入，直到输入零
    {
        cin>>n;
        if (n==0)
        {
            break;
        }
        cout<endl; //输出答案
    }
    return 0;
} 

下面是正规递推代码

//1190递推
#include
using namespace std;
long long ans[72];
int main()
{
    ans[1]=1;
    ans[2]=2;
    ans[3]=4;
    for (;;)
    {
        int n;
        cin>>n;
        if (n==0)
        {
            break;
        }
        for(int j=4;j<=n;j++)
        {
            ans[j]=ans[j-1]+ans[j-2]+ans[j-3];
        }
        cout<endl;
    }
    return 0;
}

自己感觉比记忆化好写太多也好想太多，优秀！！！！

ybt1194

这是今天分享的最后一个题啦！！！

先上题目。

【题目描述】

X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。

小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从

左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。

对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……

【输入】

输入只有一行，包括两个整数m和n（0 < m+n ≤ 20），代表方格矩阵的行数和列数，m、n之间用空格隔开。

【输出】

输出只有一行，为不同的移动路线的数目。

我们先来看，蚂蚁只能向右或向上移动。

所以……啊啊啊啊我不会递推啊！

还是乖乖搜索。

我们知道mn的数值，可以先初始化一张小地图，然后在上面搜索，枚举路径，再输出答案。

此时mn数值不大，所以用搜索是没有毛病的！！

上代码！！

//1194
#include
using namespace std;
int mapp[100][100];//初始化小地图（管他多大，不越界就行）
int m,n,way;
void dfs(int x,int y,int ex,int ey)//x,y是当前坐标，ex,ey是终点坐标
{if (x==ex&&y==ey)//如果蚂蚁走到了终点，那路径+1
    {
        way++;
        return;
    }
    if (mapp[x+1][y]!=0)
    {
        dfs(x+1,y,ex,ey);//向右走
    }
    if (mapp[x][y+1]!=0)
    {
        dfs(x,y+1,ex,ey);//向上走
    }
}
int main()
{
    cin>>m>>n;
    for (int i=m;i>0;i--)//题目要求，地图要像建坐标系一样建立
    {
        for (int j=1;j<=n;j++)
        {
            mapp[i][j]=1;//初始化小地图
        }
    }
    dfs(1,1,m,n);//从（1,1）开始走
    cout<<way;//输出答案
    return 0;
}

那么今天就先写这么多，刷题真的好累啊QAQ！！！