新人求解一道C语言铺地砖问题
铺地砖
Time Limit:1000MS Memory Limit:65536K
Total Submit:711 Accepted:224
Description
元旦过去了，新年大酬宾活动也已经告一段落了。陈盖历望着堆在仓库的瓷砖，很无聊的他把这些瓷砖裁成很多1X1 1X2 1X3的小瓷砖，然后他把这些小瓷砖排在地上画的一个1*n的长方形里。问铺满这个长方形共有多少种方法？
Input
首先输入一个整数T,表示有T组测试数据
然后是T行，每行输入1个正整数n(n<=50)
Output
对于每个n输出铺的方法种数
Sample Input
3
1
2
3
Sample Output
1
2
4
[解决办法]
假设f[n]是答案的话,明显f[n] = f[n-1]+f[n-2]+f[n-3], n > 3;
long long f[55];
long long dfs(int n)
{
if(f[n]) return f[n];
if(n == 1) return f[n] = 1;
if(n == 2) return f[n] = 2;
if(n == 3) return f[n] = 4;
return f[n] = dfs(n-1) + dfs(n-2) + dfs(n-3);
}
int main()
{
int cas,n;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
printf("%lld\n", dfs(n));
}
return 0;
}
手打的,没编译过
