算法学习——递推1

时间:2021-08-09 11:14:39

递推,顾名思义,就是从一个小问题一步步推出问题的结果。在这个过程中,最主要的就是发现其中的递推关系。

给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来,这样的式子就叫做递推关系。

来看一个问题:“未名湖边的烦恼”

问题描述:
  每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
  每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
输入格式
  两个整数,表示m和n
输出格式
  一个整数,表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定: m,n∈[0,18]
 
分析:首先很明显的一点,这个问题中m必须不小于n,否则有0种排法。为了找到其中的递推关系,我们先假定还鞋的人i=1(i=1->m),这时无论j=0或1(j=1->n),排法f[i][j]始终等于1(还鞋的人排在前),在往前推的过程中,我们发现当i=j时,意味着这一步中的最后一名一定是一个租鞋的人(因为m必须>=n),那么将这最后一名去掉对前面的排法没有任何影响,故有一个递推关系:当i=j时,f[i][j]=f[i][j-1];而当i>j时,我们不知道往这步推的时候,新加入的人是还鞋的还是租鞋的,故有,当i>j,f[i][j]=f[i-1][j]+f[i][j-1]; 至此,递推关系已经很明朗了。
以下是实现代码:
#include"iostream"
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    int a[19][19]={0};
    for(int i=1;i<=m;i++)
        a[i][0]=1;    //预处理
    for(int i=1;i<=n;i++)
        a[0][i]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                a[i][j]=a[i][j-1];
            else if(i>j)
                    a[i][j]=a[i-1][j]+a[i][j-1];
        }
    cout<<a[m][n];
    return 0;
}