TopCoder SRM 550 Div1 Medium PuyoPuyo

問題

同じ色のぷよがL匹くっつくと消える。
筒にぷよぷよを一匹ずつ、合計N匹いれる。
全てのぷよを入れ終えたときに、筒の中が空になっているような、
ぷよの入れ方の場合の数を求めよ。

制約条件

2≦L≦20
N≦1000

方針

dp[i][j]を、ぷよをiひき入れたときに、
全てのぷよを消すのに最低で必要なぷよの数がjひきであるような状態の場合の数とする。

すると、次に同色のぷよを入れるか、そうでないかで漸化式が立ち、DPできる。

ソースコード

const int mod = (int)1e9 + 7;
int dp[1010][1010];

class PuyoPuyo {
  public:
  int theCount(int L, int N) {
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		
		rep(i, N){
			(dp[i + 1][L - 1] += dp[i][0] * 4ll % mod) %= mod;
			for(int j = 1; j < N; j++){
				(dp[i + 1][j - 1] += dp[i][j]) %= mod;
				if(j + L - 1 < N) (dp[i + 1][j + L - 1] += dp[i][j] * 3ll % mod) %= mod;
			}
		}
		return dp[N][0];
  }
};