HDOJ 2046 骨牌铺方格 【递推】
铺2*1只有一种情况（一竖）
2*2有两种情况（两横或两竖）
2*n (n≥3)时
可以先铺1块竖着，再铺n-1块
还有先铺2块横着（两块竖着和第一种有重复），再铺n-2块
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
注意long long & I64d
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 typedef long long ll; 5 int n; 6 ll f[55]; 7 void Pre(){ 8 f[1] = 1; 9 f[2] = 2; 10 for(int i = 3; i <= 50; i++) f[i] = f[i-1] + f[i-2]; 11 } 12 13 int main(){ 14 Pre(); 15 while(~scanf("%d", &n)) printf("%I64d ", f[n]); 16 return 0; 17 }
版权声明：本文为博主原创文章，未经博主允许不得转载。