問題
http://community.topcoder.com/stat?c=problem_statement&pm=13437&rd=16188
・１＊Hの棒が与えられる。
・この棒を、（２H-1）＊Wのセルに敷き詰める場合の数を求める。
・WはHの倍数となる。
解き方
WがHの倍数のときにすべて敷き詰めることができる。
敷き詰め方としては、W＝３、H＝３のとき
---
---
---
---
---
が必ず１通り存在し、さらに
||
||
||
と縦に並べる並べ方がH通りあるので合計H＋１通り。
さらにWが３増えると（H+1）＊H通り＋（H+1）通りになる。
加えて、WがH+1以上のときは
上記のようにWをH個のブロック区切りで考える他に、
区切りの間に敷き詰める方法がある。
上記の３つについてｄｐを適用させていけば良い。
コード
class PlankTiling {
public: int sumup(int H, int W) {
int dp[W+1];
int MOD=1000000007;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<W;i++){
if(i+H<=W)dp[i+H]=(dp[i+H]+dp[i])%MOD;
if(i%H==0)dp[i+1]=(dp[i+1]+dp[i]*1LL*H)%MOD;
else dp[i+1]=(dp[i+1]+dp[i])%MOD;
}
return dp[W];
}
};
public: int sumup(int H, int W) {
int dp[W+1];
int MOD=1000000007;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<W;i++){
if(i+H<=W)dp[i+H]=(dp[i+H]+dp[i])%MOD;
if(i%H==0)dp[i+1]=(dp[i+1]+dp[i]*1LL*H)%MOD;
else dp[i+1]=(dp[i+1]+dp[i])%MOD;
}
return dp[W];
}
};