转自http://blog.csdn.net/cc_again/article/details/24841249

补充几点：

1.

   dp[0][0]=1; //初始状态
    dp[0][1]=0;
    dp[0][2]=0;

为什么要这样初始，是因为第0个位置无论放什么方法数都为1。所以只需在上面的三个式子中随便将一个设置为1，即可，因为看下面

 sum=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%M

所以只需在上面的三个式子中随便将一个设置为1 当i=1时 sum=1；

可是为什么

如果i>u+1时，要排除从i-1到i-u位置都放了G的情况，dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2];  而不是-dp[i-u-1][0]呢