每日一题<积木画>

根据题目来看，要求所有的排列方法，由于整个积木只有两行因此比较简单一点。dp是一个二维数组分别表示列和当前积木画的状态。0为空，1为第二层有木板第一层没有，2为第一层有木板第二层没有，3为满。

其实说白了当前列为空即上一列是满的，由此dp[i][0] = dp[i-1][3]，于是对dp的初始化便是dp[1][3] = 1,dp[1][0]= 1。

接着考虑dp[i][1]的状况，状态为1则说明当前列上行是没有木块而下层有，那么就有两种可能实现这个情况，

即可以换算成dp[i][1] = dp[i-2][3] + dp[i-1][1]。

而dp[i][2]则相反dp[i][2] = dp[i-1][0] + dp[i-1][1]。

dp[i][3]则有四种情况

由此dp[i][3] = dp[i-2][3] + dp[i-1][3] + dp[i-1][1] + dp[i-1][2]。

直接上源码

#include<iostream>
using namespace std;
int n;
long long dp[10000000][3];
#define mod 1000000007
int main()
{
  cin >> n;
  dp[0][3] = 1;
  dp[1][3] = 1;
  for (int i = 2; i <= n; i++)
  {
    dp[i][0] = dp[i - 1][3];
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
    dp[i][3] = (dp[i - 2][3] + dp[i - 1][3] + dp[i - 1][1] + dp[i - 1][2]) % mod;
  }
  cout << dp[n][3];
  return 0;
}