超哥的强迫症

超哥的强迫症

时间： 1ms        内存：128M

描述：

超哥每天都要上楼回宿舍，但是超哥每次上楼都给自己定一个跳楼所用的次数，超哥想知道他上n层楼跳m次有多少种可能。已知超哥腿长，一次能从1楼跳到3楼，也可以从1楼跳到2楼。（类似徒步爬楼 （童年趣事）问题，不过超哥厉害，一跳最少上一楼）。

输入：

多组测试数据  

每行输入两个整数n,m(1<=n<=40,1<=m<=20) 分别代表楼有n层，超哥能跳m次

输出：

每行输出一个结果

示例输入：

1 1
3 2

示例输出：

1
2

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
#include<string.h>
int sum=0;
int what(int m,int n)
{
	if(n==1)
	{
		if(m==1)
		sum++;
		else if(m==2)
		sum++;
	}
	else
	{
	what(m-1,n-1);
	what(m-2,n-1);
	}
}
int main()
{
	int a,b,i,j,*p=&sum;
	while(scanf("%d %d",&a,&b)!=EOF)
	{
		*p=0;
	what(a,b);
	printf("%d\n",sum);
	}
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstring>
#define MAX 100
using namespace std;
int m;
int n;
int dp[MAX*2][MAX];
int dfs(int n,int count=0)
{
    if(n<=0||count>=m)
    {
        if(n==0&&count==m)return 1;
        return 0;
    }
    if(dp[n][count]>=0)return dp[n][count];
    int t=0;
    t+=dfs(n-2,count+1)+dfs(n-1,count+1);
    return dp[n][count]=t;
}
int main()
{
    while(cin>>n>>m)
    {
        memset(dp,-1,sizeof(dp));
        dfs(n);
		int t=dp[n][0];
		if(t!=-1)
        cout<<t<<endl;
		else cout<<0<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。