1. 項(xiàng)目概述從數(shù)字三角形到經(jīng)典模型動態(tài)規(guī)劃DP是算法學(xué)習(xí)路上的一道分水嶺也是面試中區(qū)分候選人水平的關(guān)鍵。很多朋友一聽到“狀態(tài)轉(zhuǎn)移方程”就頭疼感覺像在解天書。其實(shí)動態(tài)規(guī)劃的核心思想非常樸素把大問題拆成小問題記住已經(jīng)解決過的小問題的答案避免重復(fù)計(jì)算。今天我們不談那些空泛的理論直接從一個最經(jīng)典、最直觀的模型入手——數(shù)字三角形模型。這個模型是理解二維坐標(biāo)系下動態(tài)規(guī)劃的絕佳起點(diǎn)它像一把鑰匙能幫你打開“摘花生”、“方格取數(shù)”、“傳紙條”等一系列經(jīng)典問題的大門。我剛開始學(xué)DP時也是從數(shù)字三角形“爬”過來的。這個模型之所以重要是因?yàn)樗昝赖卣故玖藙討B(tài)規(guī)劃的兩個核心要素狀態(tài)表示和狀態(tài)計(jì)算。狀態(tài)表示就是“我們用什么來描述當(dāng)前局面”在數(shù)字三角形里通常就是用二維坐標(biāo)(i, j)來表示“走到第i行第j列這個位置”。狀態(tài)計(jì)算就是“當(dāng)前局面的答案能從哪些更小的、已經(jīng)解決的局面的答案推導(dǎo)出來”在數(shù)字三角形里就是“從上方的兩個位置走過來選一條最優(yōu)路徑”。掌握了這個模型的精髓你會發(fā)現(xiàn)后面很多看似復(fù)雜的題目比如在網(wǎng)格里摘花生、計(jì)算最低通行費(fèi)、甚至兩個人同時走網(wǎng)格傳紙條其內(nèi)核都是數(shù)字三角形模型的變種或擴(kuò)展。它們的狀態(tài)定義和轉(zhuǎn)移邏輯有著深刻的血緣關(guān)系。本篇內(nèi)容我將帶你徹底吃透這個模型不僅分析其原理還會用C手把手實(shí)現(xiàn)五個經(jīng)典例題數(shù)字三角形、摘花生、最低通行費(fèi)用、方格取數(shù)、傳紙條并分享我在刷題和教學(xué)中總結(jié)出的、那些普通題解里不會告訴你的“避坑指南”和“優(yōu)化心法”。2. 數(shù)字三角形模型的核心思想與狀態(tài)設(shè)計(jì)2.1 模型抽象把問題裝進(jìn)網(wǎng)格數(shù)字三角形模型解決的問題通常發(fā)生在一個二維的網(wǎng)格或三角形網(wǎng)格中。我們有一個明確的起點(diǎn)通常是左上角或頂點(diǎn)一個明確的終點(diǎn)通常是右下角或底邊某個位置以及一系列明確的移動規(guī)則比如只能向下、向右走。我們的目標(biāo)是從起點(diǎn)到終點(diǎn)按照規(guī)則移動使得路徑上經(jīng)過的“數(shù)字”可以理解為價值、成本、分?jǐn)?shù)等之和滿足某種最優(yōu)條件最大或最小。為什么叫“數(shù)字三角形”最初的原型問題就是在一個三角形的數(shù)字陣列中從頂部走到底部求路徑最大和。因?yàn)樗慕Y(jié)構(gòu)像三角形所以得名。但這個模型的思維方式完全可以平移到矩形的網(wǎng)格中。這個模型的核心在于我們將整個行走過程分解成了一個個按順序抵達(dá)的“狀態(tài)”。每個狀態(tài)由你在網(wǎng)格中的位置(i, j)唯一確定。我們定義f[i][j]為從起點(diǎn)走到位置(i, j)時所能獲得的某種最優(yōu)值如最大和、最小成本。這個f[i][j]就是我們所說的“狀態(tài)”。2.2 狀態(tài)轉(zhuǎn)移當(dāng)前答案從何而來定義了狀態(tài)接下來最關(guān)鍵的一步就是建立狀態(tài)之間的聯(lián)系也就是狀態(tài)轉(zhuǎn)移方程。這是動態(tài)規(guī)劃的靈魂。在基礎(chǔ)的數(shù)字三角形或只能向下、向右走的網(wǎng)格中到達(dá)(i, j)這個位置只能從它的上方(i-1, j)或者左方(i, j-1)走過來假設(shè)起點(diǎn)在左上終點(diǎn)在右下。不可能從其他地方憑空跳過來。這就是所謂的“拓?fù)湫颉北ＷC了我們在計(jì)算f[i][j]時f[i-1][j]和f[i][j-1]一定已經(jīng)被計(jì)算出來了。那么f[i][j]的值就應(yīng)該等于從起點(diǎn)到(i-1, j)的最優(yōu)值加上(i, j)位置本身的值w[i][j]或者從起點(diǎn)到(i, j-1)的最優(yōu)值加上w[i][j]。我們要根據(jù)問題要求選擇“最大”或“最小”。 因此狀態(tài)轉(zhuǎn)移方程通常寫作f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]求最大和 或f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]求最小成本這就是最樸素的狀態(tài)轉(zhuǎn)移。對于原始的數(shù)字三角形問題行走方向?yàn)橄蛳禄蛳蛴蚁路匠虅t變?yōu)閒[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]注意這里隱藏了一個非常重要的細(xì)節(jié)——邊界處理。對于第一行i0和第一列j0的位置它們沒有“上方”或“左方”的狀態(tài)。因此我們需要在初始化或狀態(tài)轉(zhuǎn)移時進(jìn)行特殊處理。通常的做法是將f數(shù)組初始化為一個不可能的值求最大值時初始化為負(fù)無窮求最小值時初始化為正無窮然后將起點(diǎn)f[0][0]初始化為w[0][0]。在狀態(tài)轉(zhuǎn)移時需要判斷(i-1, j)和(i, j-1)是否合法即坐標(biāo)是否在網(wǎng)格內(nèi)再參與計(jì)算。另一種更簡潔的做法是將f數(shù)組多開一圈行和列都從1開始計(jì)數(shù)并將這一圈初始化為“哨兵”值如求最大值時第0行和第0列初始化為負(fù)無窮這樣在計(jì)算f[1][1]及以后時就可以統(tǒng)一使用轉(zhuǎn)移方程無需額外判斷。我強(qiáng)烈推薦第二種“多開一圈”的做法它能極大簡化代碼邏輯減少出錯可能。2.3 模型的價值為什么它是基礎(chǔ)你可能會問這個模型看起來這么簡單有什么用它的巨大價值在于其可擴(kuò)展性。今天分析的五個例題就是在這個核心模型上通過增加不同的“約束條件”和“問題維度”演化而來的。數(shù)字三角形模型的原型行走方向受限左下/右下。摘花生模型在矩形網(wǎng)格上的直接應(yīng)用行走方向受限向下/向右求最大和。最低通行費(fèi)用同樣是矩形網(wǎng)格行走方向受限向下/向右但求的是最小成本。這提醒我們狀態(tài)轉(zhuǎn)移方程中的max和min需要根據(jù)問題靈活選擇。方格取數(shù)引入了“兩個人同時走”這一新維度。狀態(tài)從描述一個人的位置(i, j)升級為描述兩個人的位置(i1, j1, i2, j2)。這是模型從二維向高維的拓展但其核心的“狀態(tài)表示狀態(tài)轉(zhuǎn)移”思想一脈相承。傳紙條可以看作是“方格取數(shù)”問題的一個變體通常增加了“每個數(shù)字只能被取一次”的約束即使兩個人經(jīng)過同一個格子。這要求我們在狀態(tài)轉(zhuǎn)移時對兩人走到同一格的情況進(jìn)行特殊判斷和處理。通過這五個由淺入深的例題你能清晰地看到動態(tài)規(guī)劃模型是如何像搭積木一樣從簡單到復(fù)雜構(gòu)建起來的。理解了這個過程你再遇到新的網(wǎng)格類DP問題就不會無從下手而是能主動去分析它的狀態(tài)應(yīng)該如何定義在基礎(chǔ)模型上增加了哪些限制狀態(tài)轉(zhuǎn)移需要如何調(diào)整3. 核心例題深度剖析與C實(shí)現(xiàn)理論講得再多不如一行代碼來得實(shí)在。接下來我們逐一拆解這五個經(jīng)典例題我會給出清晰的思路分析和可以直接“抄作業(yè)”的C代碼實(shí)現(xiàn)。代碼中會包含詳細(xì)的注釋并指出一些容易踩坑的地方。3.1 例題一數(shù)字三角形原型問題描述給定一個層數(shù)為n的數(shù)字三角形從頂部出發(fā)在每一結(jié)點(diǎn)可以選擇移動至其左下方的結(jié)點(diǎn)或右下方的結(jié)點(diǎn)一直走到底層要求找出一條路徑使路徑上的數(shù)字之和最大。思路分析 這是最標(biāo)準(zhǔn)的模型。狀態(tài)f[i][j]表示從頂點(diǎn)走到第i行第j列假設(shè)行和列都從1開始的所有路徑中數(shù)字和的最大值。 由于只能從左上(i-1, j-1)或正上(i-1, j)走過來所以狀態(tài)轉(zhuǎn)移方程為f[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]初始化f[1][1] w[1][1]頂點(diǎn)。 最終答案max(f[n][j])其中j從1到n底層所有位置中的最大值。C代碼實(shí)現(xiàn)#include iostream #include algorithm using namespace std; const int N 510, INF 1e9; int w[N][N]; // 存儲數(shù)字三角形 int f[N][N]; // dp狀態(tài)數(shù)組 int main() { int n; cin n; // 讀入數(shù)據(jù)注意三角形不是矩形第i行有i個數(shù) for (int i 1; i n; i) for (int j 1; j i; j) cin w[i][j]; // 初始化為了處理邊界我們將f數(shù)組全部初始化為負(fù)無窮 // 這樣那些“不可能”的狀態(tài)如三角形外的位置就不會被選中 for (int i 0; i n; i) for (int j 0; j i 1; j) // 注意這里j的范圍要到i1因?yàn)橛疑辖且部赡鼙辉L問 f[i][j] -INF; // 基礎(chǔ)狀態(tài)起點(diǎn) f[1][1] w[1][1]; // 狀態(tài)計(jì)算從第二行開始 for (int i 2; i n; i) for (int j 1; j i; j) f[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]; // 遍歷最后一行找出最大值 int res -INF; for (int j 1; j n; j) res max(res, f[n][j]); cout res endl; return 0; }實(shí)操心得初始化成負(fù)無窮-INF是關(guān)鍵一步。如果不這樣做對于邊界上的點(diǎn)如最左邊的點(diǎn)只有f[i-1][j]是合法的f[i-1][j-1]是非法索引在max比較時未初始化的f[i-1][j-1]可能是一個隨機(jī)的大正數(shù)導(dǎo)致錯誤地選中這條不存在的路徑。將非法狀態(tài)初始化為一個“極差”的值就能保證它們不會被選為最優(yōu)解。3.2 例題二摘花生問題描述一個R行C列的網(wǎng)格每個格子有若干花生。從左上角(1,1)出發(fā)每次只能向下或向右走到達(dá)右下角(R,C)。求能摘到的花生最大總數(shù)。思路分析 這是數(shù)字三角形模型在矩形網(wǎng)格上的直接應(yīng)用。狀態(tài)f[i][j]表示從(1,1)走到(i,j)能摘到的花生最大數(shù)量。 狀態(tài)轉(zhuǎn)移f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]。 初始化f[1][1] w[1][1]?；蛘吒ㄓ玫膶[0][*]和f[*][0]初始化為0因?yàn)閺木W(wǎng)格外走進(jìn)來是沒有花生的然后從(1,1)開始正常轉(zhuǎn)移。 最終答案f[R][C]。C代碼實(shí)現(xiàn)#include iostream #include algorithm using namespace std; const int N 110; int w[N][N], f[N][N]; int main() { int T; cin T; while (T--) { int R, C; cin R C; for (int i 1; i R; i) for (int j 1; j C; j) cin w[i][j]; // 初始化我們可以選擇將第0行和第0列初始化為0 // 這樣f[1][1] max(f[0][1], f[1][0]) w[1][1] 0 w[1][1]結(jié)果正確 // 代碼中可以省略顯式初始化因?yàn)槿謹(jǐn)?shù)組默認(rèn)值為0 // for (int i 0; i R; i) f[i][0] 0; // for (int j 0; j C; j) f[0][j] 0; for (int i 1; i R; i) for (int j 1; j C; j) f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]; cout f[R][C] endl; } return 0; }避坑技巧對于這種“多組測試數(shù)據(jù)”的題目一定要記得在每組數(shù)據(jù)開始前清空或重新初始化f數(shù)組。如果使用全局?jǐn)?shù)組由于上一組數(shù)據(jù)的結(jié)果還殘留著會導(dǎo)致下一組計(jì)算錯誤。簡單的做法是像上面一樣在while(T--)循環(huán)內(nèi)直接定義f數(shù)組C局部變量默認(rèn)值不確定但這里我們會在計(jì)算中覆蓋或者使用memset在循環(huán)開始前清空。我更喜歡在循環(huán)內(nèi)定義邏輯更清晰。3.3 例題三最低通行費(fèi)用問題描述一個N x N的網(wǎng)格每個格子有一個正整數(shù)表示經(jīng)過該格子的費(fèi)用。從左上角(1,1)出發(fā)走到右下角(N,N)每步只能向下或向右走。求所需的最低通行費(fèi)用。思路分析 這道題幾乎是“摘花生”的鏡像問題只不過把求“最大值”換成了求“最小值”。狀態(tài)定義不變f[i][j]表示從(1,1)走到(i,j)所需的最低費(fèi)用。 狀態(tài)轉(zhuǎn)移f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]。關(guān)鍵區(qū)別在于初始化因?yàn)榍笞钚≈滴覀冃枰獙數(shù)組初始化為一個很大的數(shù)如0x3f3f3f3f這個數(shù)在ACM競賽中常被用作“無窮大”的近似值因?yàn)樗鼭M足0x3f3f3f3f 0x3f3f3f3f不會溢出int且足夠大。同時起點(diǎn)(1,1)的費(fèi)用就是w[1][1]所以f[1][1]應(yīng)初始化為w[1][1]。但為了統(tǒng)一轉(zhuǎn)移公式我們通常將f[0][1]和f[1][0]初始化為0這樣f[1][1] min(f[0][1], f[1][0]) w[1][1] 0 w[1][1]。C代碼實(shí)現(xiàn)#include iostream #include cstring #include algorithm using namespace std; const int N 110, INF 0x3f3f3f3f; int w[N][N], f[N][N]; int main() { int n; cin n; for (int i 1; i n; i) for (int j 1; j n; j) cin w[i][j]; // 初始化因?yàn)榍笞钚≈迪热恐脼闊o窮大 memset(f, 0x3f, sizeof f); // 設(shè)置邊界條件從虛擬的“網(wǎng)格外”走進(jìn)(1,1)點(diǎn)費(fèi)用為0 f[0][1] f[1][0] 0; // 也可以這樣初始化直接設(shè)置f[1][1]但需要調(diào)整循環(huán)起點(diǎn) // f[1][1] w[1][1]; for (int i 1; i n; i) for (int j 1; j n; j) // 如果采用設(shè)置f[1][1]的方式這里i和j要從1開始并且要判斷i1j1的情況 // 采用設(shè)置f[0][1]和f[1][0]的方式代碼更統(tǒng)一 f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]; cout f[n][n] endl; return 0; }注意事項(xiàng)0x3f3f3f3f是一個約等于10^9的數(shù)對于大多數(shù)題目中的費(fèi)用累加是足夠大的。使用memset按字節(jié)賦值時0x3f會填充到每個字節(jié)因此int變量的四個字節(jié)都會變成0x3f最終值就是0x3f3f3f3f。這是競賽編程中的一個常用技巧。3.4 例題四方格取數(shù)問題描述設(shè)有N x N的方格圖某些方格中放有正整數(shù)。某人從左上角的A(1,1)點(diǎn)出發(fā)可以向下或向右走直到到達(dá)右下角的B(N,N)點(diǎn)。在走過的路上他可以取走方格中的數(shù)取走后方格中將變?yōu)閿?shù)字0。此人從A點(diǎn)到B點(diǎn)共走兩次求能取得的數(shù)字之和最大是多少。思路分析 這是數(shù)字三角形模型的第一次重大升級從一個人走一次變成同一個人走兩次。一個最直接的思路是先走第一次取走數(shù)然后走第二次。但問題在于第一次走的選擇會影響第二次走時網(wǎng)格的狀態(tài)有些格子變空了。這使得問題變得復(fù)雜難以分步處理。一個經(jīng)典的技巧是將兩次行走視為同時進(jìn)行。我們想象有兩個人A和B同時從(1,1)出發(fā)走向(N,N)每個人都只能向下或向右走。這樣我們需要一個狀態(tài)來同時描述兩個人的位置。定義狀態(tài)f[k][i1][i2]k表示兩個人走過的步數(shù)之和。因?yàn)槊恳徊矫總€人只能向下或向右走一格所以從起點(diǎn)開始當(dāng)兩人共走了k步時A的坐標(biāo)是(i1, k-i1)B的坐標(biāo)是(i2, k-i2)。這里i1和i2分別是兩人所在的行號。通過k和行號可以唯一確定列號。這樣就把四維狀態(tài)(i1, j1, i2, j2)優(yōu)化到了三維(k, i1, i2)這是一個非常重要的優(yōu)化。f[k][i1][i2]表示兩個人分別走到(i1, k-i1)和(i2, k-i2)時已經(jīng)取到的數(shù)字之和的最大值。狀態(tài)轉(zhuǎn)移每個人上一步都有兩種可能從上來或從左來所以組合起來共有2x24種轉(zhuǎn)移方式A從上B從上f[k-1][i1-1][i2-1]A從上B從左f[k-1][i1-1][i2]A從左B從上f[k-1][i1][i2-1]A從左B從左f[k-1][i1][i2]對于當(dāng)前格子(i1, j1)和(i2, j2)如果兩個位置不同i1 ! i2意味著j1 ! j2因?yàn)閗相同那么可以取走兩個格子的數(shù)。如果兩個位置相同即兩個人走到了同一個格子那么這個格子的數(shù)只能被取走一次。所以狀態(tài)轉(zhuǎn)移方程為f[k][i1][i2] max(四種轉(zhuǎn)移來源) t其中t是本次走到的兩個格子所能獲得的數(shù)字之和。如果i1 i2兩人同格則t w[i1][k-i1]否則t w[i1][k-i1] w[i2][k-i2]。初始化f[2][1][1] w[1][1]起點(diǎn)步數(shù)k2因?yàn)閺?1,1)到(1,1)走了0步這里需要仔細(xì)定義。通常我們定義k為橫縱坐標(biāo)之和這樣起點(diǎn)(1,1)的k2。那么f[2][1][1]就是初始狀態(tài)值為起點(diǎn)的數(shù)字。 最終答案f[2*N][N][N]終點(diǎn)(N,N)的橫縱坐標(biāo)之和為2N。C代碼實(shí)現(xiàn)#include iostream #include algorithm using namespace std; const int N 15; int w[N][N]; int f[N * 2][N][N]; // f[k][i1][i2] int main() { int n; cin n; int a, b, c; while (cin a b c, a || b || c) w[a][b] c; // k從2開始因?yàn)槠瘘c(diǎn)(1,1)的ij2 for (int k 2; k n n; k) { for (int i1 1; i1 n; i1) { for (int i2 1; i2 n; i2) { int j1 k - i1, j2 k - i2; // 判斷坐標(biāo)是否合法 if (j1 1 j1 n j2 1 j2 n) { int t w[i1][j1]; if (i1 ! i2) t w[i2][j2]; // 不是同一個格子加兩份 int x f[k][i1][i2]; // 四種狀態(tài)轉(zhuǎn)移 x max(x, f[k-1][i1-1][i2-1] t); // 下下 x max(x, f[k-1][i1-1][i2] t); // 下右 x max(x, f[k-1][i1][i2-1] t); // 右下 x max(x, f[k-1][i1][i2] t); // 右右 } } } } cout f[n n][n][n] endl; return 0; }深度解析為什么狀態(tài)定義成f[k][i1][i2]是可行的關(guān)鍵在于在只能向下和向右走的規(guī)則下當(dāng)總步數(shù)k即橫縱坐標(biāo)之和固定時知道了行號i列號j就唯一確定了j k - i。這利用了行走規(guī)則帶來的約束將四維狀態(tài)壓縮到了三維大大降低了空間和時間復(fù)雜度從O(N^4)降到O(N^3)。這是解決此類“雙路徑”問題的核心技巧務(wù)必理解透徹。3.5 例題五傳紙條問題描述一個M行N列的矩陣每個格子有一個正整數(shù)。有兩條傳紙條的路徑都是從左上角(1,1)到右下角(M,N)且路徑除了起點(diǎn)和終點(diǎn)外不能有交點(diǎn)。求兩條路徑上數(shù)字之和的最大值。思路分析 這道題與“方格取數(shù)”非常相似都是兩個人從左上到右下。區(qū)別在于約束條件“不能有交點(diǎn)”除了起點(diǎn)和終點(diǎn)。這意味著在行走過程中任何時刻兩個人都不能走到同一個格子。如果我們直接套用“方格取數(shù)”的解法在狀態(tài)轉(zhuǎn)移時當(dāng)i1 i2即兩人同格時我們只加一次格子的值。但這并不能物理上避免“經(jīng)過”同一個格子只是避免了“重復(fù)計(jì)算”該格子的值。對于“傳紙條”問題我們需要在狀態(tài)轉(zhuǎn)移時就禁止兩人走到同一個格子的情況起點(diǎn)和終點(diǎn)除外。因此狀態(tài)定義和轉(zhuǎn)移方程與“方格取數(shù)”幾乎完全一致唯一的區(qū)別是在計(jì)算t本次獲得的數(shù)字時如果i1 i2即兩人同格我們直接跳過這種狀態(tài)不進(jìn)行更新?；蛘咴谘h(huán)內(nèi)部判斷如果i1 i2 k ! 2 k ! mn即不是起點(diǎn)也不是終點(diǎn)則continue。這里有一個重要的等價轉(zhuǎn)換可以證明“找兩條不相交路徑”的最大和等價于“找兩條路徑允許路徑相交但相交點(diǎn)的值只計(jì)算一次”的最大和。因?yàn)槿绻麅蓷l最優(yōu)路徑有交點(diǎn)我們可以通過調(diào)整其中一條路徑在交點(diǎn)附近的行進(jìn)順序得到兩條新的、和不變且不相交的路徑“繞路”思想。因此很多情況下“傳紙條”的代碼可以和“方格取數(shù)”完全一樣。但為了嚴(yán)格滿足題意“不能有交點(diǎn)”我們可以在代碼中加上同格判斷。C代碼實(shí)現(xiàn)嚴(yán)格不相交版本#include iostream #include algorithm using namespace std; const int M 55, N 55; int w[M][N]; int f[M N][M][M]; // f[k][i1][i2] int main() { int m, n; cin m n; for (int i 1; i m; i) for (int j 1; j n; j) cin w[i][j]; for (int k 2; k m n; k) { for (int i1 1; i1 m; i1) { for (int i2 1; i2 m; i2) { int j1 k - i1, j2 k - i2; if (j1 1 j1 n j2 1 j2 n) { // 關(guān)鍵判斷如果走到同一格且不是起點(diǎn)或終點(diǎn)則跳過 if (i1 i2 k ! 2 k ! m n) continue; int t w[i1][j1]; if (i1 ! i2) t w[i2][j2]; int x f[k][i1][i2]; x max(x, f[k-1][i1-1][i2-1] t); x max(x, f[k-1][i1-1][i2] t); x max(x, f[k-1][i1][i2-1] t); x max(x, f[k-1][i1][i2] t); } } } } cout f[m n][m][m] endl; return 0; }經(jīng)驗(yàn)之談在實(shí)際做題和競賽中對于“傳紙條”這類問題通常直接使用“方格取數(shù)”的代碼即允許同格但值只加一次也能通過評測。這是因?yàn)轭}目數(shù)據(jù)通常滿足“最優(yōu)解路徑可以做到不相交”的性質(zhì)或者評測系統(tǒng)沒有嚴(yán)格檢查路徑是否相交只檢查和值。但從嚴(yán)謹(jǐn)理解和應(yīng)對不同出題人意圖的角度掌握嚴(yán)格不相交的寫法更有保障。理解兩者之間的等價關(guān)系能幫助你更靈活地應(yīng)對問題變種。4. 動態(tài)規(guī)劃優(yōu)化技巧與常見問題排查通過上面五個例題我們已經(jīng)掌握了數(shù)字三角形模型的基本框架和擴(kuò)展方法。但在實(shí)際編碼和解題中還會遇到一些性能問題和細(xì)節(jié)坑點(diǎn)。這部分分享一些優(yōu)化技巧和排查問題的經(jīng)驗(yàn)。4.1 空間優(yōu)化滾動數(shù)組在“摘花生”、“最低通行費(fèi)”這類簡單的二維DP中狀態(tài)轉(zhuǎn)移方程只依賴于上一行i-1和當(dāng)前行的左邊j-1。這意味著我們并不需要保存整個N x N的f數(shù)組。我們可以只用兩行數(shù)組甚至一行來滾動更新。以“摘花生”為例狀態(tài)轉(zhuǎn)移為f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]。當(dāng)我們計(jì)算第i行時只需要第i-1行的數(shù)據(jù)。對于第i行內(nèi)部的jf[i][j-1]是剛剛計(jì)算過的本行左邊的值。因此我們可以定義一個f[2][N]的數(shù)組用i % 2來滾動。更進(jìn)一步的可以只用一個一維數(shù)組f[N]int f[N]; for (int i 1; i R; i) { for (int j 1; j C; j) { // 在計(jì)算f[j]時它原來的值代表的是上一行的f[i-1][j] // f[j-1]代表的是本行已經(jīng)計(jì)算過的f[i][j-1] f[j] max(f[j], f[j-1]) w[i][j]; } }解釋在進(jìn)入第i行的內(nèi)層循環(huán)前f[j]中存儲的是上一行i-1的結(jié)果即f[i-1][j]。在內(nèi)層循環(huán)中當(dāng)我們按j從1到C的順序計(jì)算時f[j-1]已經(jīng)被更新為本行i的結(jié)果即f[i][j-1]。所以max(f[j], f[j-1])正好對應(yīng)了max(f[i-1][j], f[i][j-1])。計(jì)算完成后f[j]被更新為f[i][j]。這樣我們用一個一維數(shù)組就完成了二維DP的計(jì)算空間復(fù)雜度從O(N^2)降到了O(N)。注意事項(xiàng)使用一維滾動數(shù)組時循環(huán)順序至關(guān)重要。必須是i從1到R行j從1到C列的順序。如果j從C到1逆序循環(huán)那么f[j-1]在計(jì)算f[j]時還是上一行的值邏輯就錯了。對于“最低通行費(fèi)”這種求最小值的問題優(yōu)化方法完全一樣。4.2 路徑記錄與方案輸出有時題目不僅要求最優(yōu)值還要求輸出具體路徑。這時我們需要在狀態(tài)轉(zhuǎn)移時額外記錄每個狀態(tài)是從哪個前驅(qū)狀態(tài)轉(zhuǎn)移過來的。以“摘花生”為例我們可以用一個pre[i][j]數(shù)組記錄走到(i,j)時上一步是來自上方(i-1,j)還是左方(i,j-1)。通常用數(shù)字表示比如0表示來自上方1表示來自左方。 在狀態(tài)轉(zhuǎn)移時if (f[i-1][j] f[i][j-1]) { f[i][j] f[i-1][j] w[i][j]; pre[i][j] 0; // 來自上方 } else { f[i][j] f[i][j-1] w[i][j]; pre[i][j] 1; // 來自左方 }輸出路徑時從終點(diǎn)(R,C)開始根據(jù)pre數(shù)組記錄的方向不斷回溯到起點(diǎn)(1,1)再將路徑逆序輸出即可。vectorpairint, int path; int i R, j C; while (i 1 || j 1) { path.push_back({i, j}); if (pre[i][j] 0) i--; else j--; } path.push_back({1, 1}); reverse(path.begin(), path.end()); for (auto p : path) cout p.first p.second endl;4.3 常見錯誤與調(diào)試技巧數(shù)組越界這是DP問題中最常見的錯誤。尤其是在處理邊界第一行、第一列時。強(qiáng)烈建議使用“多開一圈”的初始化方法并將外圍格子初始化為一個不會影響狀態(tài)轉(zhuǎn)移的值求最大初始化為負(fù)無窮求最小初始化為正無窮。這能從根本上避免復(fù)雜的邊界判斷。狀態(tài)轉(zhuǎn)移方程寫錯仔細(xì)審題明確移動規(guī)則。是“向下/向右”還是“向下/向右下”是求最大值還是最小值在“方格取數(shù)”這類高維DP中要理清所有可能的前驅(qū)狀態(tài)。初始化錯誤起點(diǎn)狀態(tài)f[1][1]必須正確初始化。對于求最小值問題其他狀態(tài)要初始化為一個很大的數(shù)確保它們能被正確更新。循環(huán)順序錯誤在二維DP中通常需要保證在計(jì)算f[i][j]時它所依賴的狀態(tài)如f[i-1][j]和f[i][j-1]都已經(jīng)計(jì)算完畢。所以通常采用i從1到nj從1到m的雙重循環(huán)順序。在使用滾動數(shù)組優(yōu)化時內(nèi)層循環(huán)的順序正序或逆序至關(guān)重要。數(shù)據(jù)類型溢出路徑和或費(fèi)用累加可能超出int范圍。如果題目給出的數(shù)字較大或網(wǎng)格較大要使用long long來定義狀態(tài)數(shù)組。調(diào)試技巧打印中間狀態(tài)在程序運(yùn)行時打印出f數(shù)組的內(nèi)容與手動模擬的小樣例進(jìn)行對比。這是最直接的調(diào)試方法。從小樣例開始不要一上來就用復(fù)雜的大數(shù)據(jù)測試。先設(shè)計(jì)一個2x2或3x3的網(wǎng)格手動計(jì)算出最優(yōu)值和路徑然后用程序跑看結(jié)果是否一致。使用斷言在關(guān)鍵步驟后加入斷言檢查數(shù)組索引是否合法、狀態(tài)值是否在合理范圍內(nèi)。5. 從模型到泛化解決更復(fù)雜的網(wǎng)格DP問題掌握了數(shù)字三角形模型及其經(jīng)典變種你已經(jīng)具備了解決一大類網(wǎng)格DP問題的基礎(chǔ)。但實(shí)際遇到的問題可能更加復(fù)雜。這里提供一些思路幫助你將這個模型泛化。5.1 行走規(guī)則的擴(kuò)展基礎(chǔ)的模型只允許向下和向右走。但問題可能允許更多方向比如“向下、向右、向右下”數(shù)字三角形原型或者“上下左右”四個方向此時通常會有“不能重復(fù)走”或“有步數(shù)限制”等額外約束。當(dāng)移動規(guī)則變化時狀態(tài)轉(zhuǎn)移方程中“前驅(qū)狀態(tài)”的來源就會增加。例如如果允許向上走那么狀態(tài)轉(zhuǎn)移就可能出現(xiàn)環(huán)需要更復(fù)雜的處理方法如最短路算法、SPFA等。在競賽中網(wǎng)格DP通常保證移動具有“拓?fù)湫颉奔床粫呋仡^路形成環(huán)。5.2 狀態(tài)屬性的增加我們之前的狀態(tài)f[i][j]只記錄了“走到(i,j)的最優(yōu)值”。但問題可能附加其他條件比如有拾取限制“最多只能取K個物品”。這時狀態(tài)需要增加一維變成f[i][j][k]表示走到(i,j)且已經(jīng)取了k個物品時的最優(yōu)值。有狀態(tài)依賴“某些格子只有滿足特定條件如擁有鑰匙才能進(jìn)入”。這時狀態(tài)也需要增加一維來表示是否擁有鑰匙。求方案數(shù)如果問題不是求最優(yōu)值而是求有多少種方式走到終點(diǎn)。那么狀態(tài)f[i][j]就表示走到(i,j)的方案數(shù)。狀態(tài)轉(zhuǎn)移方程從max/min變?yōu)榍蠛蚮[i][j] f[i-1][j] f[i][j-1]如果只能向下向右。初始化f[1][1] 1。5.3 高維狀態(tài)的壓縮技巧“方格取數(shù)”問題展示了通過尋找變量之間的關(guān)系k i j來壓縮狀態(tài)維度的方法。這是一種非常重要的優(yōu)化思想。當(dāng)狀態(tài)維度過高導(dǎo)致復(fù)雜度無法承受時就要思考狀態(tài)參數(shù)之間是否存在等式或不等式的約束能否用更少的變量來表示同樣的信息。5.4 結(jié)合其他算法思想動態(tài)規(guī)劃也常與其他算法思想結(jié)合。例如預(yù)處理先通過一次DFS或BFS計(jì)算出每個格子的某些信息如離某個目標(biāo)的距離作為DP狀態(tài)的權(quán)重或約束條件。二分答案DP驗(yàn)證當(dāng)問題要求“最大化最小值”或“最小化最大值”時可以二分這個答案然后用DP來驗(yàn)證在當(dāng)前答案限制下是否存在可行路徑。數(shù)字三角形模型是動態(tài)規(guī)劃大廈的一塊堅(jiān)實(shí)基石。它教給我們的不僅僅是幾行狀態(tài)轉(zhuǎn)移代碼更重要的是一種建模思想如何將一個問題分解為階段和狀態(tài)如何定義狀態(tài)表示如何構(gòu)建狀態(tài)之間的轉(zhuǎn)移關(guān)系以及如何通過優(yōu)化技巧讓算法更高效。當(dāng)你遇到一個新的網(wǎng)格類問題時不妨先問自己它和數(shù)字三角形模型有多像差異在哪里狀態(tài)需要增加什么維度轉(zhuǎn)移方程需要如何調(diào)整多進(jìn)行這樣的思考和實(shí)踐你解決動態(tài)規(guī)劃問題的能力一定會穩(wěn)步提升。