http://acm.hdu.edu.cn/showproblem.php?pid=2501
Tiling_easy version
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9660 Accepted Submission(s): 7361
Problem Description
有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。
Input
输入的第一行包含一个正整数T（T<=20），表示一共有 T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示网格的大小是2行N列。
Output
输出一共有多少种铺设的方法，每组数据的输出占一行。
Sample Input
3
2
8
12
Sample Output
3
171
2731
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
__INT64_TYPE__ dp[];
dp[]=;
dp[]=;
for(int i = ; i <= ; i++){
dp[i]=dp[i-]+dp[i-]*;
}
while(t--){
int n;
scanf("%d",&n);
cout << dp[n] <<endl;
}
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=2190
重建希望小学
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8584 Accepted Submission(s): 5692
Problem Descriptio
学校教室的长度为n米，宽度为3米，现在我们有2种地砖，规格分别是1米×1米，2米×2米，如果要为该教室铺设地砖，请问有几种铺设方式呢？
Input
输入数据首先包含一个正整数C，表示包含C组测试用例，然后是C行数据，每行包含一个正整数n(1<=n<=30)，表示教室的长度。
Output
对于每组测试数据，请输出铺设地砖的方案数目，每个输出占一行。
Sample Input
2
2
3
Sample Output
3
5
#include<bits/stdc++.h>
using namespace std;
int main(){
__INT64_TYPE__ dp[];
dp[]=;
dp[]=;
for(int i = ; i <= ; i++){
dp[i]=dp[i-]+dp[i-]*;
}
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
cout << dp[n] << endl;
}
return ;
}
小结：找到当前状态由上几个状态的迭代方程注意避免重复计算即可。