說實話第一次在題單里看到 Counting Towers 這個題名時我還以為又是一道“鋪滿 2×n 地板”的經(jīng)典遞推畢竟這種題在動態(tài)規(guī)劃入門題單里太常見了。結(jié)果真正上手之后才發(fā)現(xiàn)它考的并不是簡單的 f(n) f(n-1) f(n-2)而是一個典型的“狀態(tài)機 DP”你不僅要記錄已經(jīng)處理到第幾列還要額外記錄當前列和上一列之間的高度關(guān)系。這個設(shè)計點一出來整道題的難度立刻就不一樣了。如果你正在刷 Codeforces 或其他 OJ 的動態(tài)規(guī)劃題單或者準備面試時怕遇到“狀態(tài)設(shè)計”類的題目Counting Towers 值得認真做一遍。它不涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)也沒有奇怪的邊界討論但它能很好地訓(xùn)練一件事如何從一堆看似自由的選擇里提煉出真正必要的狀態(tài)。這篇文章我會從題意拆解、狀態(tài)轉(zhuǎn)移、代碼實現(xiàn)到常見坑點完整復(fù)盤一遍我的解題過程希望能幫你少走一點彎路。1. Counting Towers 的題意拆解先別急著寫遞推1.1 題目描述與第一反應(yīng)題目給我們 n 列磚塊的位置每一列都可以從地面往上搭建磚塊有兩種1×1 的小方塊和 1×2 的長磚。長磚既可以豎直放讓某一列直接長高兩格也可以橫著放同時覆蓋相鄰兩列讓兩列在同一高度各加一格。問最終搭建出來的不同塔的方案數(shù)答案對 1e97 取模。我第一次看到這個描述時腦子里最先冒出的思路是“按高度一層一層考慮”每一行可以放若干 1×1也可以在一些地方放橫著的 1×2然后逐行往上鋪。但很快我就發(fā)現(xiàn)這條路走不通因為塔的高度沒有給定如果直接按行枚舉層數(shù)是無限的根本沒法寫遞推。另一個自然的想法是仿照斐波那契那類鋪磚題令 dp[i] 表示前 i 列全部“穩(wěn)定”的方案數(shù)然后考慮最后一列怎么放。但問題在于最后一塊磚如果橫著放它會跨到第 i1 列去這樣“前 i 列完成”這件事就說不清楚。也就是說單純按列做一維遞推信息量不夠。1.2 關(guān)鍵觀察相鄰列高度差只需要關(guān)注 0 和 1真正讓我豁然開朗的是下面這個觀察在從左往右逐列構(gòu)建的過程中我們不需要知道每一列到底有多高只需要知道當前列和上一列之間的“高度差”。而高度差的情況實際上只有兩種是需要單獨記錄的當前列和上一列高度相同記為狀態(tài) 0當前列比上一列高 1記為狀態(tài) 1。為什么不是差 2、差 3因為水平放置的 1×2 磚一次只能跨越兩列。如果某時刻相鄰兩列的高度差大于 1那么高出來的那些格子既不能被水平磚“帶過去”又會導(dǎo)致后續(xù)列無法平穩(wěn)對接。從構(gòu)造角度看一個合法的塔輪廓相鄰列的高度差始終不會超過 1。你可以簡單理解為水平磚是唯一能把兩列“焊”在一起的零件而它的尺寸決定了相鄰列的臺階高度只能是一格。既然高度差只有 0 和 1 兩種情況那么 DP 狀態(tài)里就只需要給每一列額外帶一個 0/1 的標記。這就是這道題“狀態(tài)設(shè)計”的突破口把看似無限的高度信息壓縮成一個有限的狀態(tài)機。1.3 為什么不能用簡單的 f(n) f(n-1) f(n-2)在理順狀態(tài)之前我先走了不少彎路其中一個典型的錯誤想法是把橫著的 1×2 磚看成“占兩列的一整塊”于是猜測遞推是 f(n) f(n-1) f(n-2)。這個公式在 2×n 鋪磚問題里很常見但在這里行不通。原因在于Counting Towers 里同一列的高度是可以繼續(xù)往上長的。橫著的 1×2 磚并不是一個“終結(jié)塊”它只是讓兩列在某一層齊頭并進在那之后兩列都還可以繼續(xù)往上搭 1×1 或者豎磚。換句話說每一列是一個持續(xù)累積高度的過程而不是像二維鋪磚那樣每個格子放了就不能再放。這個區(qū)別決定了我們必須用“列與列的相對高度”來描述進度而不是用“還剩多少列沒鋪”。想明白了這一點之后后面的狀態(tài)轉(zhuǎn)移就順理成章了。2. 狀態(tài)設(shè)計與轉(zhuǎn)移方程把狀態(tài)機畫出來2.1 定義 dp[i][0] 和 dp[i][1]我最終采用的狀態(tài)定義是dp[i][0]前 i 列已經(jīng)完成并且第 i 列和它左邊的第 i-1 列處于同一高度的方案數(shù)。為了方便理解我把它叫“平頂狀態(tài)”。dp[i][1]前 i 列已經(jīng)完成并且第 i 列比第 i-1 列高 1 格的方案數(shù)我叫它“凸起狀態(tài)”。注意這里“前 i 列已經(jīng)完成”的意思是從第 1 列到第 i 列內(nèi)部所有磚塊都已經(jīng)正確放置不會出現(xiàn)某個格子空著等下一列來補的情況。允許存在的只有可能從第 i 列伸向第 i1 列的那些水平磚但我們用狀態(tài)的 0/1 把它們?nèi)匡@式表達出來了如果第 i 列頂部是平的說明沒有未完成的連接如果第 i 列比左邊高一格說明這里剛好有一個臺階下一步需要用水平磚把這個臺階接到右邊去。2.2 轉(zhuǎn)移方程推導(dǎo)從 dp[i-1][0] 到 dp[i][0] 有兩種方式一種是在第 i 列放一個 1×1讓它和左邊的最高層對齊另一種是在第 i 列放一個豎直的 1×2讓該列在原有基礎(chǔ)上直接長高兩格但它和左列的高度差仍然保持為 0因為左列之前也是平的所以本質(zhì)上兩者都是在原來的高度上各自加高最終高度差還是 0。所以這一項貢獻是 2 乘以 dp[i-1][0]。從 dp[i-1][1] 到 dp[i][0] 只有一種方式第 i-1 列比它左邊高出一格那么第 i 列就要放一個橫著的 1×2 磚把這個臺階補平。這個水平磚的左半嵌入第 i-1 列凸出的那個格子右半落在第 i 列對應(yīng)的位置于是第 i 列和左邊的高度差變成 0。這一項貢獻是 dp[i-1][1]。因此dp[i][0] 2 * dp[i-1][0] dp[i-1][1]再來推 dp[i][1]。想讓第 i 列最后比第 i-1 列高 1 格有兩種前置情況。第一種是前 i-1 列處在平頂狀態(tài) dp[i-1][0]此時第 i 列可以放一個橫著的 1×2 磚左半搭在第 i-1 列頂部右半落在第 i 列的某個格子上這樣第 i 列就會比左列凸出一格。第二種是前 i-1 列已經(jīng)是凸起狀態(tài) dp[i-1][1]說明第 i-1 列比它左邊高了一格那么第 i 列可以再接一個水平磚把臺階繼續(xù)向右平移最終第 i 列仍然比第 i-1 列高一格。所以dp[i][1] dp[i-1][0] dp[i-1][1]這兩個轉(zhuǎn)移式合在一起就是一個非常干凈的狀態(tài)機。注意這個狀態(tài)機的特點是dp[i][1] 右邊的兩項加起來正好等于 dp[i][0] 減去 dp[i-1][0]所以兩個狀態(tài)之間存在很明顯的內(nèi)部關(guān)聯(lián)寫代碼時不要把它當成完全獨立的兩個數(shù)組。2.3 初始值與邊界初始狀態(tài)需要單獨處理第 1 列。當只有一列時它可以放一個 1×1 方塊此時的塔是平頂?shù)膶?yīng) dp[1][0] 1也可以放一個豎直的 1×2 磚讓這一列直接高兩格但相對于“虛擬的第 0 列”它算是凸出了一格對應(yīng) dp[1][1] 1。不過實際代碼里我習慣把 dp[1][0] 設(shè)為 2、dp[1][1] 設(shè)為 1為什么因為第 1 列的“平頂”其實有兩種來源放一個 1×1或者放一個豎著的 1×2豎直磚不會造成橫向臺階因此從狀態(tài)機的角度它依然是平頂。而“凸起”狀態(tài)只有一種來源就是放一個向右伸出的水平磚等待第 2 列來補。這兩種初始化方式會直接影響轉(zhuǎn)移式里 2 倍系數(shù)是否合理所以寧可多花一分鐘在紙上把初始狀態(tài)寫清楚也不要等到樣例不過再回來猜。我這里采用的版本與下文代碼一致dp[1][0] 2dp[1][1] 1。如果你按照某個題解初始化成別的值務(wù)必確認它的狀態(tài)定義是否和我一樣否則很容易出現(xiàn)“整體平移”式的錯誤。2.4 手動模擬 n1, 2, 3 來驗證狀態(tài)機任何 DP 寫完都應(yīng)該先用小數(shù)據(jù)把狀態(tài)轉(zhuǎn)移表完整跑一遍確認沒有出現(xiàn)荒謬的負數(shù)或者突然變大得不合理的值。n1 時答案是 3也就是 dp[1][0] dp[1][1] 3。n2 時利用遞推式dp[2][0] 2 * dp[1][0] dp[1][1] 2 * 2 1 5dp[2][1] dp[1][0] dp[1][1] 2 1 3總數(shù)為 5 3 8。n3 時繼續(xù)dp[3][0] 2 * 5 3 13dp[3][1] 5 3 8總數(shù)為 13 8 21。這份數(shù)值表現(xiàn)很漂亮3、8、21恰好是斐波那契數(shù)列的偶數(shù)位項 F(4)、F(6)、F(8)。事實上可以證明 dp[n][0] F(2n-1)、dp[n][1] F(2n-2)總方案數(shù) ans F(2n)。這個性質(zhì)可以作為代碼正確性的一個強校驗同時也是一個很有意思的收尾彩蛋。3. 代碼實現(xiàn)與優(yōu)化從 O(n) 數(shù)組到滾動變量3.1 最樸素的數(shù)組版本狀態(tài)轉(zhuǎn)移只有兩個數(shù)組直接開長度為 n1 的 vector 即可。注意數(shù)據(jù)范圍如果 n 能到 1e6開兩個 long long 數(shù)組沒什么壓力但如果你習慣用 int取模運算時一定要把中間結(jié)果轉(zhuǎn)成 long long否則 2 * dp[i-1][0] 那一項在 dp 值接近 1e97 時會溢出 int。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long dp0(n 1, 0), dp1(n 1, 0); dp0[1] 2; dp1[1] 1; for (int i 2; i n; i) { dp0[i] (2 * dp0[i - 1] dp1[i - 1]) % MOD; dp1[i] (dp0[i - 1] dp1[i - 1]) % MOD; } cout (dp0[n] dp1[n]) % MOD \n; return 0; }這段代碼就是樸素版。優(yōu)點是直觀、好調(diào)試適合剛學(xué) DP 時對照狀態(tài)轉(zhuǎn)移表一步步看。缺點是當 n 很大時數(shù)組的 O(n) 空間雖然不算多但完全沒有必要。3.2 滾動數(shù)組優(yōu)化觀察遞推式可以發(fā)現(xiàn)dp[i] 只依賴 dp[i-1]所以用兩個變量滾動更新就足夠了。這也是面試中最常要求的優(yōu)化點從 O(n) 空間壓到 O(1)。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long dp0 2, dp1 1; // 對應(yīng) i1 for (int i 2; i n; i) { long long ndp0 (2 * dp0 dp1) % MOD; long long ndp1 (dp0 dp1) % MOD; dp0 ndp0; dp1 ndp1; } cout (dp0 dp1) % MOD \n; return 0; }這里有個細節(jié)值得注意不能用 dp0 (2 * dp0 dp1) % MOD 直接覆蓋然后再用新的 dp0 去算 dp1因為 ndp1 依賴的是舊的 dp0。必須先算出兩個新值再一起賦值。這種“臨時變量交換”的錯誤在滾動數(shù)組優(yōu)化里非常常見我至少見過三次有人把順序?qū)懛础?.3 與斐波那契數(shù)列的關(guān)系一個可選的優(yōu)美結(jié)論如果你把兩張表繼續(xù)寫下去n 4: dp0 34, dp1 21, 總數(shù) 55n 5: dp0 89, dp1 55, 總數(shù) 144你會發(fā)現(xiàn)總數(shù) 3, 8, 21, 55, 144 正好是 F(4), F(6), F(8), F(10), F(12)。這其實不是偶然。由 dp0[i1] 2dp0[i] dp1[i] 和 dp1[i1] dp0[i] dp1[i] 兩式相加得到dp0[i1] dp1[i1] 3dp0[i] 2dp1[i]而由 dp0[i] dp0[i] dp1[i] - dp1[i] 之類的恒等變換可以推出總數(shù)序列滿足一個更簡單的二階遞推。更直接的辦法是驗證總數(shù)序列 T(i) 滿足T(i) 3 * T(i-1) - T(i-2)比如 T(3)21, T(2)8, T(4)55正好 55 3*21 - 8。這個遞推和斐波那契偶數(shù)位的公式完全一致。實際做題時如果發(fā)現(xiàn)自己推出的 DP 結(jié)果能與某些已知數(shù)列吻合是一個很好的 sanity check。不過我不建議比賽時花太多時間去推這個閉式除非題目明確要求 n 達到 1e18 且需要用矩陣快速冪。如果真遇到超大 n由于 T(i) 滿足二階線性遞推可以用 2×2 矩陣快速冪把復(fù)雜度降到 O(log n)本質(zhì)上就是計算斐波那契數(shù)列的偶數(shù)位項。這個擴展留給有興趣的讀者自己驗證核心代碼就是把二階遞推寫成矩陣[ T(i) ] [ 3 -1 ] * [ T(i-1) ] [ T(i-1) ] [ 1 0 ] [ T(i-2) ]注意矩陣里有負系數(shù)取模時要多加上 MOD 再取模避免產(chǎn)生負數(shù)。4. 常見問題與排查技巧我踩過的坑都在這4.1 取模時機不對導(dǎo)致溢出或答案錯誤很多初學(xué)者會在遞推內(nèi)部到處取模比如每一步都對 dp0、dp1、2*dp0 分別取模。這種做法本身不錯但要特別小心 2 * dp0 這個乘法。當 dp0 已經(jīng)是一個接近 1e97 的數(shù)時2 * dp0 約等于 2e9雖然還在 32 位有符號整數(shù)范圍內(nèi)但已經(jīng)不保險了如果后面再加一個 dp1累計可能超過 2^31-1。所以要么全程用 long long要么在乘法前強制轉(zhuǎn)換。我個人的習慣是所有參與運算的變量都用 long long最后一步統(tǒng)一 % MOD。這樣代碼最清晰也不容易在中間步驟漏掉取模。4.2 狀態(tài)定義沒統(tǒng)一初始化抄錯這是最隱蔽的坑。網(wǎng)上關(guān)于 Counting Towers 的題解有很多種寫法有的把 dp[1][0] 初始化為 1有的初始化為 2有的把狀態(tài) 1 定義成“當前列比前一列矮 1”還有的定義成“當前列有一個向右伸出的半塊”。這些寫法在各自的狀態(tài)機里都是自洽的但如果你只抄轉(zhuǎn)移式、不抄狀態(tài)定義很容易出現(xiàn)“左邊初始化是平頂 2右邊轉(zhuǎn)移系數(shù)卻是 3”這種不匹配。建議你在本地寫完代碼后先用 n2 手動驗證一遍。如果答案不是 8那大概率是初始值或者轉(zhuǎn)移式里的系數(shù)出了問題。這時候不要急著亂試系數(shù)回到狀態(tài)定義重新捋一遍當前狀態(tài)到底代表什么從上一個狀態(tài)到這個狀態(tài)有哪幾種放置方式每一步都說得清楚代碼自然就對了。4.3 滾動數(shù)組覆蓋順序?qū)懛辞懊嬉呀?jīng)提到過一次這里單獨列出來是因為它太典型了。滾動數(shù)組優(yōu)化的核心是“先用舊值算新值再統(tǒng)一覆蓋”。如果你寫dp0 (2 * dp0 dp1) % MOD; dp1 (dp0 dp1) % MOD;那么第二個式子里的 dp0 已經(jīng)是更新過的值算出來的 dp1 就會偏大。這類錯誤在樣例比較小的時候特別難發(fā)現(xiàn)因為結(jié)果可能只是差一點點你不會立刻覺得“完全不對”。我的排查方法是把滾動數(shù)組優(yōu)化前后的兩份代碼各跑一遍隨機生成 n對拍一下一旦某個 n 的答案不一致就逐行對照轉(zhuǎn)移式。4.4 從這道題學(xué)到的通用 DP 思路遷移Counting Towers 最值得記住的一點不是那個具體的轉(zhuǎn)移式而是“壓縮狀態(tài)”的思維方式。很多計數(shù)題表面上看起來狀態(tài)無限比如高度、長度、數(shù)量但只要找到一個關(guān)鍵的“相對量”或“差值”就能把無限變成有限。比如這道題里的“相鄰列高度差”本質(zhì)上就是用一個布爾值來代替“高度”這個變量。類似的技巧在很多題里都會用到連續(xù)子數(shù)組的和可以用前綴和的差值表示樹上的深度可以用父子關(guān)系表示序列的 LIS 可以用末尾元素的最小值表示。下次再遇到看起來狀態(tài)很多的 DP先別急著開多維數(shù)組停下來想一想到底哪些信息是真正影響后續(xù)決策的哪些信息只是看起來重要、實際可以從其他信息推算出來就這道題而言如果你還想繼續(xù)練手可以嘗試幾個變形加入 1×3 的磚塊會怎么樣狀態(tài)會變多如果允許塔的高度為負方向延伸會怎么樣顯然不合法但這能幫你理解邊界條件的作用如果要求所有列的高度最終必須相等呢這就退化成另一種鋪磚問題了。每改一個條件狀態(tài)設(shè)計都要重新調(diào)整這個過程對鍛煉 DP 直覺非常有效。最后再分享一個小技巧做題時如果你發(fā)現(xiàn)自己的 dp 數(shù)組里某個狀態(tài)值一直用不上或者某個轉(zhuǎn)移總是乘以一個超過 2 的系數(shù)多半是狀態(tài)定義有冗余或者題目里還有隱含條件沒發(fā)現(xiàn)。Counting Towers 的轉(zhuǎn)移系數(shù)都很小2 和 1這就是狀態(tài)設(shè)計到位的一個信號。好的狀態(tài)機轉(zhuǎn)移必然是清晰、簡單、可解釋的。