题目描述

给定\(2*1\)和\(2 * 2\)两种规格的地砖，请问\(2 * n\)的地面总共有多少种方法?

下面是铺满\(2*17\)的地面的示意图。

输入输出格式

输入

多组数据，每组数据包括1行1个整数n，表示地面的长度。\((0\leq n \leq250)\)

输出

每组数据输出\(1\)行\(1\)个整数，表示铺满\(n\)米地面的方法数。

思路

因为我们知道长度为\(i\)的矩阵只能由\(i-1\)和\(i-2\)变来，又长度为一的矩阵的方法数为\(1\)，长度为二的矩阵的方法数为\(3\)，其中有一种相当于\(i-1\)的方法数，所以状态转移方程为\(dp[i][j]=dp[i-1][j]+dp[i-2][j]*2;\)

代码

#include
    
      using namespace std;  int dp[301][501];  //dp[i]用来存储第i列的结果，dp[i][0]存储长度int main(){     dp[1][0]=1;      dp[1][1]=1;      dp[2][0]=1;      dp[2][1] = 3;      for(int i=3;i<=300;i++){          int len=max(dp[i-2][0],dp[i-1][0]);        for(int j=1;j<=len;j++)             dp[i][j]=dp[i-1][j]+dp[i-2][j]*2;  //按位加        dp[i][0]=max(dp[i-2][0],dp[i-1][0]);   //取两个加数中较长的长度         for(int j=1;j<=dp[i][0];j++){            dp[i][j+1]+=dp[i][j]/10;  //进位             dp[i][j]%=10;          }          while(dp[i][dp[i][0]+1]>0){ //更新高精度加法结果的位数            dp[i][0]++;             dp[i][dp[i][0]+1]+=dp[i][dp[i][0]]/10;          }      }      int n;      while(cin>>n){         if(n==0)            cout<<1<
     
      =1;i--)                cout<