poj - 1953 - World Cup Noise（dp）

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

?

——>>设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 
  
   
#include 
   
     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: , ++nCase); printf(%d , dp[n][0] + dp[n][1]); } return 0; } 
   
  

?