多米诺和托米诺平铺

记住这一句:当前 = 前一项×2 + 前第三项,边界 dp[0]=1、dp[1]=1、dp[2]=2。系数 2 与前第三项来自 full/gap 状态消元,下面每一帧都直接套这个递推。

先填好三个边界:空棋盘 dp[0]=1(什么都不放算 1 种)、宽度 1 只能竖一块 dp[1]=1、宽度 2 有「两竖」和「两横」共 dp[2]=2。绿色这三格是递推的起点,后面 0 都会被逐格算出。

推下标 3(棋盘宽 3):紫色 dp[3] 是这一步要算的,它只看两处绿色:紧邻的 dp[2]=2 和往前数第三个 dp[0]=1。

套公式:dp[3] = 2×dp[2] + dp[0] = 2×2 + 1 = 5。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[3] 落格为 5(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。

推下标 4(棋盘宽 4):紫色 dp[4] 是这一步要算的,它只看两处绿色:紧邻的 dp[3]=5 和往前数第三个 dp[1]=1。

套公式:dp[4] = 2×dp[3] + dp[1] = 2×5 + 1 = 11。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[4] 落格为 11(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。

推下标 5(棋盘宽 5):紫色 dp[5] 是这一步要算的,它只看两处绿色:紧邻的 dp[4]=11 和往前数第三个 dp[2]=2。

套公式:dp[5] = 2×dp[4] + dp[2] = 2×11 + 2 = 24。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[5] 落格为 24(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。

推下标 6(棋盘宽 6):紫色 dp[6] 是这一步要算的,它只看两处绿色:紧邻的 dp[5]=24 和往前数第三个 dp[3]=5。

套公式:dp[6] = 2×dp[5] + dp[3] = 2×24 + 5 = 53。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[6] 落格为 53(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。

推下标 7(棋盘宽 7):紫色 dp[7] 是这一步要算的,它只看两处绿色:紧邻的 dp[6]=53 和往前数第三个 dp[4]=11。

套公式:dp[7] = 2×dp[6] + dp[4] = 2×53 + 11 = 117。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[7] 落格为 117(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。

推下标 8(棋盘宽 8):紫色 dp[8] 是这一步要算的,它只看两处绿色:紧邻的 dp[7]=117 和往前数第三个 dp[5]=24。

套公式:dp[8] = 2×dp[7] + dp[5] = 2×117 + 24 = 258。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。

dp[8] 落格为 258(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,到这里 dp[8] 已是最后一格,接着回看整条数组。

推到底:dp[8] = 258,就是 2×8 棋盘的全部铺法数。整条 dp 数组 [1, 1, 2, 5, 11, 24, 53, 117, 258] 一路只靠「前一项×2 + 前第三项」生长出来。

边界:n=1 得 1、n=2 得 2、n=3 起进入递推得 5。

两个延伸:三变量滚动压成 O(1);辅助状态消元可严谨推出方程。