1. 這門(mén)課到底在考什么先看2023期末討論里都出現(xiàn)了哪些影子每年期末前總有同學(xué)到處搜“某某大學(xué)算法設(shè)計(jì)與分析期末原題”我也不例外。拿到湖南大學(xué)2023年網(wǎng)傳的那份期末題目討論時(shí)我第一反應(yīng)不是去看具體答案而是先把整份題目的考點(diǎn)分布拉了一個(gè)清單?？赐曛笥袀€(gè)很強(qiáng)烈的感受題目可以千變?nèi)f化但核心考法非常固定選擇題、簡(jiǎn)答題、編程題基本都圍繞那十幾個(gè)經(jīng)典模型在打轉(zhuǎn)。算法設(shè)計(jì)與分析這門(mén)課和數(shù)據(jù)結(jié)構(gòu)最大的區(qū)別在于數(shù)據(jù)結(jié)構(gòu)考你“這個(gè)東西怎么組織”算法設(shè)計(jì)與分析考你“這個(gè)問(wèn)題怎么解、為什么這么解、復(fù)雜度是多少”。期末試卷表面上是幾個(gè)大題實(shí)際上是在測(cè)你有沒(méi)有建立一套算法思維。所謂算法思維說(shuō)白了就是三件事第一拿到問(wèn)題能不能快速判斷該用分治、動(dòng)態(tài)規(guī)劃、貪心還是回溯第二能不能把解決方案寫(xiě)得讓機(jī)器執(zhí)行而不是只會(huì)背概念第三能不能說(shuō)清楚這個(gè)方案的時(shí)間復(fù)雜度、空間復(fù)雜度以及為什么它比其他方案好。2023年的期末討論里選擇題部分出現(xiàn)了很多復(fù)雜度比較的題比如讓你判斷某個(gè)遞歸式對(duì)應(yīng)的時(shí)間復(fù)雜度或者比較不同排序算法在特定數(shù)據(jù)下的表現(xiàn)。這類題在哪個(gè)學(xué)校都逃不掉因?yàn)閺?fù)雜度分析是整個(gè)課程的骨架。簡(jiǎn)答題則集中在動(dòng)態(tài)規(guī)劃的兩個(gè)核心性質(zhì)、貪心算法與動(dòng)態(tài)規(guī)劃的區(qū)別、分支限界與回溯的異同這些老生常談的點(diǎn)上。編程題部分一眼掃過(guò)去就是0-1背包、最長(zhǎng)公共子序列、最短路徑、活動(dòng)安排這幾個(gè)經(jīng)典模型的變體。所以不要被“原題”兩個(gè)字帶偏。真正有價(jià)值的不是記住某一道題怎么解而是透過(guò)這些題目看到老師想考核的知識(shí)點(diǎn)其實(shí)是一個(gè)封閉的集合。把這套知識(shí)點(diǎn)吃透了任意換數(shù)字、換背景、換描述方式你都能認(rèn)出來(lái)它背后到底在考什么。2. 把考點(diǎn)按優(yōu)先級(jí)排序別平均用力2.1 動(dòng)態(tài)規(guī)劃永遠(yuǎn)站在C位不管哪個(gè)學(xué)校的算法設(shè)計(jì)與分析試卷動(dòng)態(tài)規(guī)劃都是絕對(duì)的大頭湖南大學(xué)2023年的討論里同樣如此。選擇題會(huì)有狀態(tài)轉(zhuǎn)移方程的理解題簡(jiǎn)答題會(huì)讓你寫(xiě)出最優(yōu)子結(jié)構(gòu)和無(wú)后效性的定義編程題更是直接來(lái)一道DP題。動(dòng)態(tài)規(guī)劃之所以被反復(fù)考是因?yàn)樗C合考察了問(wèn)題建模能力、遞推思維和編碼實(shí)現(xiàn)能力這三樣恰恰是程序員最核心的基本功。備考動(dòng)態(tài)規(guī)劃我建議不要一上來(lái)就刷題先把幾個(gè)最經(jīng)典的模型吃透0-1背包、完全背包、最長(zhǎng)公共子序列、最長(zhǎng)遞增子序列、矩陣連乘、編輯距離。這六個(gè)模型覆蓋了絕大多數(shù)DP題的套路。比如最長(zhǎng)公共子序列屬于“雙序列DP”狀態(tài)定義是dp[i][j]表示第一個(gè)序列前i個(gè)字符和第二個(gè)序列前j個(gè)字符的LCS長(zhǎng)度0-1背包屬于“單序列容量約束”的DP狀態(tài)定義是dp[i][j]表示前i個(gè)物品在容量為j的背包里能裝的最大價(jià)值。你把這些模型的狀態(tài)定義、初始化、轉(zhuǎn)移方程、遍歷順序全部手寫(xiě)一遍比看十遍課件都管用。動(dòng)態(tài)規(guī)劃還有一個(gè)容易被忽略的點(diǎn)不是所有最優(yōu)子結(jié)構(gòu)問(wèn)題都能用DP還要滿足無(wú)后效性。我的理解是無(wú)后效性就是說(shuō)當(dāng)前狀態(tài)一旦確定后續(xù)決策只與當(dāng)前狀態(tài)有關(guān)不會(huì)去關(guān)心之前是怎么走到這個(gè)狀態(tài)的?？荚嚂r(shí)如果問(wèn)“為什么這道題可以用DP”你要答出三點(diǎn)問(wèn)題具有最優(yōu)子結(jié)構(gòu)、無(wú)后效性、子問(wèn)題重疊。少一個(gè)都不完整。2.2 分治與遞歸復(fù)雜度分析是送分題也是送命題分治算法在期末考試?yán)锖苌賳为?dú)出大編程題但它幾乎是所有后續(xù)算法的地基。歸并排序、快速排序、二分查找、大整數(shù)乘法、Strassen矩陣乘法這些經(jīng)典分治案例的遞推式和時(shí)間復(fù)雜度基本是選擇題和簡(jiǎn)答題的?？?。比如問(wèn)你T(n)2T(n/2)O(n)的復(fù)雜度答案就是O(nlogn)T(n)T(n/1)O(1)就是O(logn)。這類題只要熟練掌握主定理基本就是送分。但很多人栽在細(xì)節(jié)上主定理的三種情況分不清遞歸式的邊界條件忽略或者把分治和動(dòng)態(tài)規(guī)劃搞混。我當(dāng)年就犯過(guò)這個(gè)錯(cuò)誤看到“把大問(wèn)題分解成小問(wèn)題”就以為是分治其實(shí)動(dòng)態(tài)規(guī)劃同樣也是把大問(wèn)題分解成子問(wèn)題。兩者的本質(zhì)區(qū)別在于分治的子問(wèn)題是相互獨(dú)立的而動(dòng)態(tài)規(guī)劃的子問(wèn)題會(huì)重疊。這個(gè)區(qū)別在簡(jiǎn)答題里特別容易考一定要記準(zhǔn)。2.3 貪心、回溯與分支限界常以對(duì)比的面目出現(xiàn)貪心算法在期末卷面上通常作為編程大題出現(xiàn)比如活動(dòng)安排、最小生成樹(shù)、單源最短路徑的Dijkstra算法、哈夫曼編碼。這些例子有個(gè)共同特點(diǎn)每一步都做當(dāng)前看起來(lái)最優(yōu)的選擇且這個(gè)局部最優(yōu)能推出全局最優(yōu)?？荚嚂r(shí)如果出一道貪心題很可能要求你證明貪心選擇性質(zhì)。很多同學(xué)只會(huì)寫(xiě)算法不會(huì)證明這是復(fù)習(xí)的大漏洞。其實(shí)證明思路很固定先假設(shè)存在一個(gè)最優(yōu)解然后通過(guò)交換論證說(shuō)明貪心選擇不會(huì)使解變差最后用數(shù)學(xué)歸納法或反證法收尾。回溯和分支限界在編程題里出現(xiàn)的概率相對(duì)低一些但在簡(jiǎn)答題里幾乎每學(xué)期都有。要搞清楚四個(gè)關(guān)鍵差異回溯是深度優(yōu)先搜索所有解空間分支限界是廣度優(yōu)先或最小耗費(fèi)優(yōu)先搜索回溯的目標(biāo)通常是找出所有解分支限界的目標(biāo)通常是找一個(gè)最優(yōu)解回溯用?；蜻f歸實(shí)現(xiàn)分支限界用隊(duì)列或優(yōu)先隊(duì)列實(shí)現(xiàn)回溯的剪枝函數(shù)只判斷可行性分支限界還需要考慮限界函數(shù)。把這張對(duì)比表背熟簡(jiǎn)答題基本穩(wěn)了。2.4 圖算法期末卷面上的常青樹(shù)圖算法在2023年的討論里同樣占了不少篇幅。Dijkstra、Floyd、Prim、Kruskal、拓?fù)渑判颉㈥P(guān)鍵路徑這些都是高頻考點(diǎn)。我的經(jīng)驗(yàn)是圖算法題很少要求你從零發(fā)明算法更多是考察你“會(huì)不會(huì)用代碼實(shí)現(xiàn)經(jīng)典算法”以及“能不能對(duì)手寫(xiě)例子手動(dòng)模擬一遍算法過(guò)程”。所以備考時(shí)光看懂PPT不夠一定要在紙上手動(dòng)跑一遍Dijkstra的整個(gè)過(guò)程把每個(gè)節(jié)點(diǎn)的dist值和前驅(qū)節(jié)點(diǎn)一個(gè)個(gè)寫(xiě)出來(lái)。圖算法還有一個(gè)容易踩的坑使用場(chǎng)景混淆。Dijkstra不能處理負(fù)權(quán)邊Floyd可以處理負(fù)權(quán)邊但不能有負(fù)權(quán)回路Bellman-Ford可以檢測(cè)負(fù)權(quán)回路Prim適合稠密圖Kruskal適合稀疏圖。這些邊界條件記清楚選擇題才能不丟分。3. 編程題實(shí)戰(zhàn)把經(jīng)典模型變成肌肉記憶3.1 0-1背包從遞歸到DP一個(gè)模型吃透動(dòng)態(tài)規(guī)劃期末編程題如果考動(dòng)態(tài)規(guī)劃0-1背包的變體出現(xiàn)頻率極高。不要一上來(lái)就寫(xiě)二維DP先試著用遞歸描述問(wèn)題然后改成記憶化搜索最后再優(yōu)化成DP這個(gè)過(guò)程能幫你徹底理解狀態(tài)轉(zhuǎn)移。下面是一個(gè)最基礎(chǔ)的0-1背包實(shí)現(xiàn)語(yǔ)言用Pythondef knapsack(weights, values, capacity): n len(weights) # dp[i][j] 表示前 i 個(gè)物品背包容量為 j 時(shí)的最大價(jià)值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 1): if weights[i - 1] j: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] return dp[n][capacity]這段代碼里的狀態(tài)轉(zhuǎn)移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1])。含義是當(dāng)前第i個(gè)物品我有兩種選擇不裝進(jìn)背包那就繼承前i-1個(gè)物品在容量j下的最優(yōu)值裝進(jìn)背包那就騰出w[i-1]的空間加上當(dāng)前物品的價(jià)值?？荚嚂r(shí)如果編程題出背包大概率不是讓你原樣寫(xiě)這個(gè)基礎(chǔ)版而是在物品數(shù)量、選擇規(guī)則、約束條件上改一改。但只要你吃透了上面這個(gè)模板認(rèn)出來(lái)它是背包并不難。還可以繼續(xù)優(yōu)化成一維數(shù)組因?yàn)閐p[i][j]只依賴dp[i-1]這一行。優(yōu)化時(shí)有個(gè)關(guān)鍵點(diǎn)容量j必須從大往小遍歷否則同一個(gè)物品會(huì)被重復(fù)選。這個(gè)細(xì)節(jié)特別適合考選擇題和簡(jiǎn)答題比如給出一個(gè)一維數(shù)組版本的代碼問(wèn)為什么第二層循環(huán)要倒序遍歷。答案很簡(jiǎn)單正序遍歷會(huì)把當(dāng)前物品多次放入背包等價(jià)于完全背包。3.2 最短路徑代碼模板Dijkstra和Floyd怎么選圖算法編程題里最短路徑是熱門(mén)。考慮到考試時(shí)間限制Dijkstra用優(yōu)先隊(duì)列實(shí)現(xiàn)是最穩(wěn)妥的既能跑稠密圖也能跑稀疏圖代碼量適中。下面是一份可以快速默寫(xiě)的模板import heapq def dijkstra(graph, start, n): # graph[u] [(v, weight), ...] dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist寫(xiě)這道題的時(shí)候有幾個(gè)容易錯(cuò)的地方。第一綠點(diǎn)判斷可以省略因?yàn)槿绻麖亩牙飶棾龅膁已經(jīng)大于dist[u]說(shuō)明這個(gè)節(jié)點(diǎn)已經(jīng)被更新過(guò)了直接跳過(guò)。第二初始化時(shí)dist[start]0其他節(jié)點(diǎn)為正無(wú)窮不能漏。第三堆中元素是元組(dist, node)排序會(huì)先按dist排所以dist要放在前面。這三個(gè)點(diǎn)任何一個(gè)搞錯(cuò)程序都會(huì)出問(wèn)題或者邏輯對(duì)但效率低。如果題目里要求任意兩點(diǎn)之間的最短路徑而且邊權(quán)可能為負(fù)那就不要猶豫用Floyd。Floyd的核心是一個(gè)三重循環(huán)def floyd(graph, n): # graph[i][j] 直接存儲(chǔ)權(quán)重不存在則設(shè)為 inf dist [[graph[i][j] for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist很多同學(xué)問(wèn)Floyd的三層循環(huán)為什么k一定要放在最外層我的理解是k代表“允許經(jīng)過(guò)的前k個(gè)節(jié)點(diǎn)”這本身是一種從小到大遞推的過(guò)程。如果把k放在內(nèi)層就變成了“某一次路徑計(jì)算時(shí)允許經(jīng)過(guò)某個(gè)節(jié)點(diǎn)”這并不能保證全局最優(yōu)結(jié)果就會(huì)錯(cuò)。這個(gè)解釋在考場(chǎng)上如果被問(wèn)到可以直接說(shuō)外層k本質(zhì)是在枚舉中間節(jié)點(diǎn)集合的規(guī)模和DP中的階段是一樣的概念。3.3 寫(xiě)代碼前先寫(xiě)五分鐘偽代碼考場(chǎng)上編程題最忌諱的是拿到題就敲代碼。我記得當(dāng)年有同學(xué)一上來(lái)就噼里啪啦寫(xiě)寫(xiě)了一半發(fā)現(xiàn)狀態(tài)定義不對(duì)又全部擦掉白白浪費(fèi)十五分鐘。我的習(xí)慣是先用兩三分鐘在草稿紙上寫(xiě)出關(guān)鍵四件事?tīng)顟B(tài)定義、初始化、轉(zhuǎn)移方程、遍歷順序。對(duì)于圖算法再加上一個(gè)數(shù)據(jù)結(jié)構(gòu)選擇是用鄰接矩陣還是鄰接表是用數(shù)組模擬隊(duì)列還是用優(yōu)先隊(duì)列。這五分鐘不會(huì)浪費(fèi)。把偽代碼寫(xiě)清楚之后再往代碼語(yǔ)言里翻譯出錯(cuò)率會(huì)低很多。還有一個(gè)小技巧如果時(shí)間緊張寫(xiě)代碼時(shí)用變量名短一點(diǎn)沒(méi)關(guān)系但一定要讓自己看得懂?？紙?chǎng)上你是不需要給代碼寫(xiě)注釋的但變量名最好能表達(dá)含義比如dp、dist、prev這樣檢查時(shí)方便也方便老師判卷時(shí)讀懂你的思路。萬(wàn)一最終代碼有小bug至少思路分能保住。4. 簡(jiǎn)答題和概念題背什么、怎么答才不丟分4.1 P、NP、NPC這些概念先把邏輯鏈條理清算法設(shè)計(jì)與分析課程最后總會(huì)講計(jì)算復(fù)雜性理論這也是期末簡(jiǎn)答題的必考區(qū)。很多同學(xué)對(duì)P、NP、NPC的概念背了又忘原因是沒(méi)理解這條邏輯鏈。P類問(wèn)題指的是能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題NP類問(wèn)題指的是能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問(wèn)題。注意NP全稱是Non-deterministic Polynomial不是Non-Polynomial這一點(diǎn)選擇題特別愛(ài)挖坑。如果一個(gè)問(wèn)題既能多項(xiàng)式時(shí)間求解又想找一個(gè)多項(xiàng)式驗(yàn)證方法它顯然屬于P也屬于NP。所以P類問(wèn)題是NP類問(wèn)題的子集只不過(guò)學(xué)界至今沒(méi)證明P是否等于NP。NPC問(wèn)題則是NP類問(wèn)題里“最難”的一類它的定義是首先它屬于NP其次所有NP問(wèn)題都能在多項(xiàng)式時(shí)間內(nèi)歸約到它。換句話說(shuō)只要有一個(gè)NPC問(wèn)題能被多項(xiàng)式時(shí)間求解那所有NP問(wèn)題都能被多項(xiàng)式時(shí)間求解P就等于NP了。期末如果讓你舉NPC問(wèn)題常見(jiàn)的有旅行商問(wèn)題、三色圖問(wèn)題、哈密頓回路、子集和問(wèn)題。把這些例子記熟簡(jiǎn)答題至少能寫(xiě)出一半內(nèi)容。4.2 動(dòng)態(tài)規(guī)劃性質(zhì)的表述要專業(yè)化2023年的簡(jiǎn)答題里動(dòng)態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)和無(wú)后效性幾乎是必問(wèn)題。很多同學(xué)能說(shuō)出大概意思但表述不嚴(yán)謹(jǐn)導(dǎo)致扣分。最優(yōu)子結(jié)構(gòu)的標(biāo)準(zhǔn)說(shuō)法是一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。無(wú)后效性的標(biāo)準(zhǔn)說(shuō)法是某階段狀態(tài)一旦確定此后的決策只依賴當(dāng)前狀態(tài)與之前如何到達(dá)該狀態(tài)無(wú)關(guān)。這里我提供一個(gè)答題模板問(wèn)“為什么該問(wèn)題可以用動(dòng)態(tài)規(guī)劃求解”時(shí)分三步答。第一步指出問(wèn)題具有最優(yōu)子結(jié)構(gòu)并簡(jiǎn)單舉例說(shuō)明最優(yōu)解中包含子問(wèn)題的最優(yōu)解第二步指出各階段決策具有無(wú)后效性當(dāng)前狀態(tài)即可描述未來(lái)決策所需的所有信息第三步指出子問(wèn)題存在重疊若用遞歸會(huì)有大量重復(fù)計(jì)算因此用動(dòng)態(tài)規(guī)劃存儲(chǔ)中間結(jié)果。這三步寫(xiě)下來(lái)答案不僅完整還能體現(xiàn)你是真的理解而不是死記硬背。4.3 對(duì)比題是送分題但一定要寫(xiě)全對(duì)比維度期末考試特別喜歡出對(duì)比類簡(jiǎn)答題比如“回溯法與分支限界法的異同”“Dijkstra與Prim算法的區(qū)別”“動(dòng)態(tài)規(guī)劃與貪心算法的區(qū)別”。這類題的答題技巧是不要只寫(xiě)一句“一個(gè)用DFS一個(gè)用BFS”而是從目標(biāo)、搜索方式、適用條件、數(shù)據(jù)結(jié)構(gòu)、時(shí)間復(fù)雜度、典型應(yīng)用等維度逐條對(duì)照。比如動(dòng)態(tài)規(guī)劃與貪心算法可以從三個(gè)維度答適用條件上DP要求最優(yōu)子結(jié)構(gòu)且子問(wèn)題重疊貪心要求貪心選擇性質(zhì)求解方式上DP自底向上或自頂向下求解所有子問(wèn)題貪心每一步只做一個(gè)局部最優(yōu)決策證明難度上DP的證明一般依賴數(shù)學(xué)歸納法貪心需要證明貪心選擇的正確性通常用交換論證。這樣一對(duì)比閱卷老師一眼就能看出你掌握了知識(shí)點(diǎn)。5. 復(fù)習(xí)計(jì)劃與考場(chǎng)時(shí)間分配這是一場(chǎng)策略游戲5.1 四周復(fù)習(xí)計(jì)劃按周拆解任務(wù)期末復(fù)習(xí)最忌諱從頭到尾看一遍課件。課件只是知識(shí)的索引真正幫你提分的是動(dòng)手寫(xiě)題。我建議把復(fù)習(xí)周期設(shè)為四周每周一個(gè)主題周末做一次綜合自測(cè)。第一周集中攻克復(fù)雜度分析和分治法把所有遞歸式分析題做完主定理的三種情況要爛熟于心。第二周全身心投入動(dòng)態(tài)規(guī)劃把0-1背包、最長(zhǎng)公共子序列、最長(zhǎng)遞增子序列、編輯距離等經(jīng)典題自己親手實(shí)現(xiàn)一遍并試著不看題解講出狀態(tài)轉(zhuǎn)移過(guò)程。第三周主攻貪心算法和圖算法重點(diǎn)手動(dòng)模擬Dijkstra、Prim、Kruskal、拓?fù)渑判虻恼w流程。第四周回歸簡(jiǎn)答題和概念題把P、NP、NPC、最優(yōu)子結(jié)構(gòu)、貪心選擇性質(zhì)這些概念梳理成自己的答題模板每天默寫(xiě)一遍。這里有個(gè)細(xì)節(jié)每周的周末自測(cè)一定要計(jì)時(shí)嚴(yán)格按照考試時(shí)間來(lái)做。不光是檢驗(yàn)知識(shí)掌握程度更是訓(xùn)練你在壓力下做題的狀態(tài)。很多同學(xué)平時(shí)寫(xiě)得很好一到考場(chǎng)就慌就是因?yàn)槿鄙傧迺r(shí)模擬訓(xùn)練。自測(cè)完不必追求滿分重點(diǎn)看哪些題目卡了超過(guò)十分鐘這些卡頓點(diǎn)就是你下周需要補(bǔ)的漏洞。5.2 考場(chǎng)上的時(shí)間分配前松后緊最致命我觀察過(guò)很多期末卷面發(fā)現(xiàn)不及格的同學(xué)通常不是不會(huì)做而是時(shí)間分配出了問(wèn)題。有的在前面的選擇題上糾結(jié)太久導(dǎo)致后面的編程題沒(méi)時(shí)間寫(xiě)有的在最后一道大題上死磕結(jié)果前面簡(jiǎn)單題白白丟分。這里分享一套我的時(shí)間分配策略適用于大多數(shù)算法考試。假設(shè)考試時(shí)長(zhǎng)120分鐘總分100分。選擇題和填空題建議控制在25到30分鐘內(nèi)完成這些題考察的是記憶和理解會(huì)就會(huì)不會(huì)就標(biāo)記一下先跳過(guò)千萬(wàn)不能戀戰(zhàn)。簡(jiǎn)答題建議控制在30分鐘內(nèi)每題寫(xiě)個(gè)四五行條理清晰就行不要長(zhǎng)篇大論。剩下的60分鐘留給編程題和算法設(shè)計(jì)題。拿到編程題先用5分鐘在草稿紙上列狀態(tài)定義和轉(zhuǎn)移方程再用25分鐘實(shí)現(xiàn)最后留10分鐘檢查邊界條件。如果編程題寫(xiě)完之后還有時(shí)間一定要回頭檢查自己標(biāo)記過(guò)的選擇題和填空題。往往就是在你頭腦最清醒的時(shí)候之前拿不準(zhǔn)的題突然就有思路了。還有一點(diǎn)如果編程題實(shí)在寫(xiě)不出來(lái)不要空著把你想到的狀態(tài)定義、轉(zhuǎn)移方程、甚至只是大致的算法框架都寫(xiě)上去。很多學(xué)校是按步驟給分的一個(gè)正確的狀態(tài)定義就能拿到寶貴的幾分。5.3 復(fù)習(xí)資料怎么用原題不等于答案回到文章開(kāi)頭的問(wèn)題搜到“湖南大學(xué)算法設(shè)計(jì)與分析2023期末考試原題”到底有沒(méi)有用我的答案是有用但用法不是背答案。原題最大的價(jià)值是幫你劃出考點(diǎn)范圍和出題風(fēng)格讓你知道老師偏愛(ài)考哪類知識(shí)點(diǎn)、編程題愛(ài)用哪些經(jīng)典模型做基底。拿到原題之后你應(yīng)該做的是把每一道題對(duì)應(yīng)到教材的知識(shí)點(diǎn)然后去找相同知識(shí)點(diǎn)的其他題目練習(xí)而不是把原題答案背下來(lái)。我一貫的看法是算法這門(mén)課靠背是背不出來(lái)的。你背下了一道0-1背包題的代碼考試時(shí)出個(gè)完全背包變體你還是得從頭分析。相反如果你真正理解了“狀態(tài)定義”和“狀態(tài)轉(zhuǎn)移”這兩個(gè)核心概念無(wú)論題目怎么變換你都能寫(xiě)出正確的代碼。所以復(fù)習(xí)的時(shí)候優(yōu)先級(jí)永遠(yuǎn)是把原理搞懂其次才是刷題最后才是看原題。6. 高頻錯(cuò)題與避坑實(shí)錄這些細(xì)節(jié)決定了你能多拿十分6.1 動(dòng)態(tài)規(guī)劃的三個(gè)常見(jiàn)坑第一個(gè)坑是初始化不對(duì)。很多DP問(wèn)題里dp[0][j]和dp[i][0]這些邊界值不是0而是正無(wú)窮或負(fù)無(wú)窮取決于你是求最小值還是最大值。比如編輯距離中dp[0][j] jdp[i][0] i因?yàn)閺囊粋€(gè)空串變成長(zhǎng)度為j的串需要j次插入操作。如果初始化時(shí)一律填0結(jié)果就全錯(cuò)了。判斷初始化是否正確我的經(jīng)驗(yàn)是手動(dòng)驗(yàn)證一個(gè)最小的例子比如dp[1][1]看看它是否符合直覺(jué)。第二個(gè)坑是遍歷順序不對(duì)。如果是一維DP背包容量循環(huán)方向會(huì)決定是“每個(gè)物品只能選一次”還是“每個(gè)物品可以選很多次”這一點(diǎn)上文已經(jīng)說(shuō)過(guò)了。如果是二維DP遍歷順序?qū)Y(jié)果影響不大但要注意狀態(tài)依賴的是上一行還是本行左側(cè)。比如說(shuō)最長(zhǎng)公共子序列里dp[i][j]依賴dp[i-1][j]、dp[i-1][j-1]、dp[i][j-1]那i和j都從前往后遍歷就行但如果是編輯距離dp[i][j]也依賴dp[i-1][j-1]同樣從前往后遍歷沒(méi)問(wèn)題。關(guān)鍵是動(dòng)手前先畫(huà)一張二維表把每個(gè)格子的依賴關(guān)系畫(huà)出來(lái)遍歷順序就一目了然。第三個(gè)坑是狀態(tài)轉(zhuǎn)移方程漏掉一種情況。比如最長(zhǎng)遞增子序列中dp[i]表示以第i個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度它依賴所有滿足ji且a[j]a[i]的dp[j]加1最后取最大值。很多同學(xué)只寫(xiě)了一個(gè)“dp[i] dp[i-1] 1”這是錯(cuò)的因?yàn)檫f增子序列不一定連續(xù)dp[i]和前一個(gè)元素不一定有直接關(guān)系。要想避開(kāi)這個(gè)坑拿到題先想一想我當(dāng)前這個(gè)狀態(tài)到底能由哪些“前一個(gè)狀態(tài)”轉(zhuǎn)移過(guò)來(lái)把所有可能性列全再寫(xiě)方程。6.2 圖算法題里容易被忽略的邊界圖算法編程題里最常見(jiàn)的錯(cuò)誤是用鄰接矩陣但忘記處理重邊。如果兩個(gè)節(jié)點(diǎn)之間有多條邊鄰接矩陣存儲(chǔ)時(shí)應(yīng)該保留最小權(quán)值否則Dijkstra或Prim會(huì)拿到一個(gè)較大的邊權(quán)影響最短路徑或最小生成樹(shù)結(jié)果。鄰接表則天然支持重邊但代價(jià)是遍歷時(shí)可能多處理幾條邊?？紙?chǎng)上如果你發(fā)現(xiàn)樣例數(shù)據(jù)可以通過(guò)但提交卻超時(shí)可以先想想是不是圖存儲(chǔ)方式選錯(cuò)了。另一個(gè)坑是節(jié)點(diǎn)編號(hào)從0開(kāi)始還是從1開(kāi)始。如果題目給的是1到n的節(jié)點(diǎn)而你的數(shù)組長(zhǎng)度是n初始化dist數(shù)組時(shí)要給下標(biāo)0留一個(gè)空位或者干脆把所有下標(biāo)減1統(tǒng)一成從0開(kāi)始。這個(gè)問(wèn)題看似低級(jí)但每年都會(huì)有人因?yàn)橄聵?biāo)越界而丟分。我的習(xí)慣是代碼里第一行就把“本代碼所有節(jié)點(diǎn)統(tǒng)一從0開(kāi)始”寫(xiě)進(jìn)注釋然后所有數(shù)組都按n來(lái)開(kāi)不給自己留犯錯(cuò)的機(jī)會(huì)。還有一個(gè)容易忽略的點(diǎn)如果題目中的圖不一定連通Dijkstra之后未訪問(wèn)到的節(jié)點(diǎn)dist會(huì)被初始化為正無(wú)窮輸出時(shí)要按題目要求處理比如輸出-1。很多同學(xué)默認(rèn)所有節(jié)點(diǎn)都能被訪問(wèn)到結(jié)果輸出了一堆inf白白丟了測(cè)試點(diǎn)的分。預(yù)處理時(shí)先想想圖是否連通、是否可能有孤立節(jié)點(diǎn)這比盲目寫(xiě)代碼更重要。6.3 復(fù)雜度分析題別忘記常數(shù)和log復(fù)雜度分析的選擇題和填空題經(jīng)?？家恍翱此坪?jiǎn)單但容易算錯(cuò)”的題。常見(jiàn)的坑有三個(gè)忽略循環(huán)條件中的乘除關(guān)系把O(nlogn)寫(xiě)成O(n^2)忽略遞歸式中每一項(xiàng)的規(guī)模直接把T(n)2T(n/2)O(n)寫(xiě)成O(n)忽略常數(shù)因子把O(2n)和O(n)當(dāng)成不同的復(fù)雜度。關(guān)于最后一點(diǎn)我特意提出來(lái)是因?yàn)楹芏喑鯇W(xué)者會(huì)誤以為常數(shù)會(huì)影響大O結(jié)果。其實(shí)量級(jí)分析只看增長(zhǎng)速度2n和n都?xì)w為O(n)。考場(chǎng)上如果選擇題問(wèn)“以下哪個(gè)和O(n)等價(jià)”千萬(wàn)別選“2n”這種選項(xiàng)因?yàn)樗峭粋€(gè)量級(jí)只是寫(xiě)法不同。至于遞歸式分析最穩(wěn)妥的方法是背熟主定理的三種情況再結(jié)合手工展開(kāi)驗(yàn)證一遍。熟練之后你在考場(chǎng)上連草稿紙都不用翻就能寫(xiě)出答案。6.4 用手寫(xiě)模擬代替純腦補(bǔ)是復(fù)習(xí)階段最高效的方法有些知識(shí)點(diǎn)比如Dijkstra的過(guò)程、Prim的選邊過(guò)程、拓?fù)渑判虻某鲫?duì)順序光看代碼很難形成直覺(jué)。我強(qiáng)烈建議復(fù)習(xí)時(shí)準(zhǔn)備一張白紙手動(dòng)跑一遍完整流程。以Dijkstra為例把每個(gè)節(jié)點(diǎn)的dist值用一個(gè)表格列出來(lái)每次選最小dist節(jié)點(diǎn)更新鄰居然后在表格里劃掉已確定的節(jié)點(diǎn)。整個(gè)過(guò)程手寫(xiě)三遍你自然就理解了為什么已經(jīng)彈出的節(jié)點(diǎn)不需要再更新。這個(gè)方法對(duì)回溯算法同樣有效。畫(huà)一棵解空間樹(shù)從根節(jié)點(diǎn)出發(fā)按DFS順序遍歷標(biāo)出哪些節(jié)點(diǎn)被剪枝、為什么被剪枝。當(dāng)你能把一棵樹(shù)的剪枝過(guò)程畫(huà)得明明白白分支限界和回溯的區(qū)別也就迎刃而解。很多時(shí)候我們覺(jué)得算法抽象只是因?yàn)槟X子里缺少一個(gè)可以依賴的圖像。手寫(xiě)模擬就是把這個(gè)圖像刻進(jìn)腦子里最直接的方式比抄十遍代碼都管用。7. 最后說(shuō)一點(diǎn)關(guān)于“原題”的個(gè)人體會(huì)我是支持大家去找原題的但一定要帶著腦子找。算法設(shè)計(jì)與分析這門(mén)課核心考點(diǎn)就那么多原題最大的作用其實(shí)是讓你快速鎖定復(fù)習(xí)范圍而不是讓你投機(jī)取巧。我見(jiàn)過(guò)太多同學(xué)花三天時(shí)間背原題答案結(jié)果考試時(shí)題目稍微換了個(gè)說(shuō)法連“這題考的是動(dòng)態(tài)規(guī)劃”都看不出來(lái)。反而是那些把經(jīng)典模型踏踏實(shí)實(shí)練過(guò)幾遍的人即使沒(méi)見(jiàn)過(guò)原題也能從考場(chǎng)出來(lái)時(shí)心里有底。最后再分享一個(gè)我踩過(guò)很多次坑之后總結(jié)的小技巧考前最后一天不要再做新題了。把你整理好的狀態(tài)轉(zhuǎn)移方程、圖算法模板、復(fù)雜度分析方法一條一條默寫(xiě)出來(lái)只看自己不熟悉的部分。真正到了考場(chǎng)上你就會(huì)發(fā)現(xiàn)緊張感會(huì)消化的不是知識(shí)而是信心。當(dāng)你看到那道所謂的新題腦子里能立刻蹦出“這不就是0-1背包一個(gè)變體嘛”的時(shí)候你就已經(jīng)在及格線之上了。