poj - 1953 - World Cup Noise（dp）

题意：n位长的01序列(0 < n < 45)，但不能出现连续的两个1，问序列有多少种。

题目链接：http://poj.org/problem?id=1953

——>>设dp[i][j]表示前 i 位中第 i 位为 j 时的序列数，则状态转移方程为：

dp[i][0] = dp[i - 1][0] + dp[i - 1][1];

dp[i][1] = dp[i - 1][0];

因为对于相同的n，其结果是固定的，所以可以对一个n只计算一次，然后记住她。。

#include <cstdio>
#include <cstring>const int MAXN = 45 + 1;int n;
int dp[MAXN][2];void Init()
{memset(dp, -1, sizeof(dp));
}void Dp(int i)
{if (i == 1){dp[i][0] = dp[i][1] = 1;return;}if (dp[i][0] != -1){return;}Dp(i - 1);dp[i][0] = dp[i - 1][0] + dp[i - 1][1];dp[i][1] = dp[i - 1][0];
}int main()
{int T, nCase = 0;scanf("%d", &T);while (T--){scanf("%d", &n);Init();Dp(n);printf("Scenario #%d:\n", ++nCase);printf("%d\n\n", dp[n][0] + dp[n][1]);}return 0;
}