從資訊理論到動態規劃：用「零錢兌換」讀懂演算法題背後的思維框架

在技術學習中，很多人會把「數學基礎」和「演算法刷題」切成兩條平行線：學資訊理論時覺得概念抽象、公式偏理論；做動態規劃時又只盯著狀態轉移和程式碼模板，彷彿只要把套路背熟就能過題。Dev.to AI 這篇來自 PixelBank 學習計畫的內容，恰恰試圖打通這兩者之間的距離。它一方面回到資訊理論的核心問題，討論資訊如何被度量、如何面對不確定性、如何在約束下做出更有效的表達；另一方面又落到「零錢兌換」這一經典程式設計題，展示理論思維如何幫助我們更清楚地理解演算法設計，而不是把題目當作單純的記憶練習。

資訊理論之所以重要，不只是因為它在通訊、壓縮、編碼、機器學習等領域有悠久歷史，更因為它提供了一種處理複雜問題的基本視角：面對大量可能性時，怎樣用儘量簡潔、儘量穩定、儘量低成本的方式去組織資訊。無論是香農意義上的熵，還是更廣義上的不確定性度量，本質上都在回答一個問題：當系統存在多種可能狀態時，我們需要多少「資訊」才能把它描述清楚，或者說，我們怎樣才能避免無效的重複描述。

把這個視角搬到演算法題中，很多經典問題立刻會變得更容易理解。所謂演算法，不只是把輸入映射為輸出，它同時也是一種「資訊處理流程」。一個好的演算法會盡可能減少重複計算，把已經獲得的資訊保留下來，把後續決策建立在既有結果之上，從而降低整體求解成本。動態規劃恰恰是這種思想最典型的體現：如果同一個子問題會被反覆遇到，那麼就不該每次都從頭計算，而應該把它記下來；如果一個大問題的最優解可以由更小問題的最優解拼出來，那麼就說明問題具有可復用的結構。

「零錢兌換」之所以經典，正因為它是這種思想的入門範例。題目的基本形式通常是：給定若干硬幣面額，以及一個目標金額，問最少需要多少枚硬幣才能湊出這個金額；如果無法湊出，則回傳無法達成的標記。乍看之下，它像是一道簡單的組合題，很多初學者會先想到貪心法：每次優先選最大面額，儘快逼近目標值。但只要題目面額設計得稍微複雜一點，這種直覺就會失效。原因在於，局部上「看起來最省」的選擇，未必能導向全域最優結果。

這正是資訊理論視角能介入的地方。對於零錢兌換而言，真正關鍵的不是某一步選了哪枚硬幣，而是「在目前金額剩餘條件下，我們掌握了什麼資訊，接下來還需要什麼資訊」。如果把每個金額都看成一個狀態，那麼求解目標金額的過程，實際上就是不斷利用較小金額狀態的資訊，去構造較大金額狀態的資訊。這裡的資訊不是抽象口號，而是非常具體的：湊成金額 i 所需的最少硬幣數，是否可達，若可達則由哪個前置狀態轉移而來。

從這個角度看，動態規劃並不是憑空出現的模板，而是對問題資訊結構的一種壓縮表達。原始問題如果用暴力搜尋來做，會生成大量重複路徑：同一個剩餘金額，可能透過不同順序、不同組合反覆出現。比如目標金額是某個較大數值時，從不同分支遞迴下去，最終常常會抵達同一個「剩餘 7」「剩餘 11」之類的中間狀態。如果每次遇到這些狀態都重新計算，那麼系統實際上在不斷重複處理同一份資訊，效率自然會迅速惡化。

而動態規劃所做的事情，就是把這些重複的資訊統一收束。我們定義一個陣列，令 dp[i] 表示湊成金額 i 所需的最少硬幣數。初始條件通常設為 dp[0] = 0，因為湊出金額 0 不需要任何硬幣。對於其他金額，先假設它們不可達，或者賦予一個足夠大的初始值。隨後遍歷每個金額，再嘗試每一種硬幣面額：如果目前金額 i 至少能減去某個硬幣 c，並且 dp[i - c] 已經可達，那麼 dp[i] 就有機會被更新為 dp[i - c] + 1。最後，dp[target] 就給出了答案。

這一過程看似只是常規狀態轉移，實際上背後包含了非常清晰的資訊處理邏輯。首先，dp[i] 不是對所有組合的完整保存，而是對「最優結果」的壓縮保存。也就是說，演算法主動捨棄了大量對最終目標無用的細節，只保留決策所需的最少資訊。其次，每次更新都建立在一個前提之上：我們相信較小狀態中已經濃縮了足夠可靠的資訊，因此不必重新展開它的全部生成過程。這種「保留必要資訊，丟棄冗餘細節」的思想，與資訊理論中高效表達的精神高度一致。

如果進一步拆解，「零錢兌換」還是一堂關於狀態設計的好課。很多初學者做動態規劃時最痛苦的地方，不是程式碼寫不出來，而是不知道「狀態到底該怎麼定義」。資訊理論式的思考可以提供一個判斷標準：一個好的狀態，應該既能完整承載後續決策所需資訊，又不過度冗餘。以本題為例，我們並不需要記錄每一種硬幣已經用了多少枚，也不必保留所有可能組合，只需要知道「湊成目前金額的最優成本是多少」。這說明該問題的未來決策，與歷史路徑的具體順序無關，只與目前金額的最優值有關。換句話說，過去的資訊可以被壓縮成一個足夠小、但仍然有效的表示。

這也是很多優秀演算法設計共同具備的特徵：找到恰到好處的資訊邊界。狀態太少，資訊不夠，後續無法決策；狀態太多，資訊冗餘，演算法複雜度會失控。學習演算法時，真正拉開差距的並不是是否見過某道題，而是能否在新問題裡辨識出「哪些資訊必須保留，哪些資訊可以捨棄」。從這個意義上說，資訊理論不是離刷題很遠的理論，它反而像一把非常底層的尺子，用來衡量你的建模是否緊湊、表達是否經濟。

「零錢兌換」還涉及另一個常被忽視的訓練點：最優性與可達性是兩層不同的資訊。對很多人來說，寫動態規劃時最容易混亂的，是把「這個金額能不能湊出來」和「如果能湊出來，最少要幾枚」混在一起。實際上，先判斷可達，再比較最優，是更穩定的思路。不可達狀態並不是空白，它本身也是一種資訊。只有明確地區分「無解」和「已有解但不夠優」，轉移方程才不容易出錯。這與資訊處理中的邊界定義非常相似：一個系統如果連「未知」「無值」「錯誤」「可用但次優」這些狀態都不區分清楚，後續處理必然會混亂。

從教學角度看，把資訊理論和零錢兌換放在一起，還有一層更現實的意義。今天不少學習內容都在強調「會做題」，卻較少解釋「為什麼這種方法合理」。結果就是，讀者能在短時間內記住若干經典題模板，卻缺少遷移能力。一旦題目稍微變形，比如變成「求組合數量」「求是否可達」「求恰好裝滿的最大價值」「硬幣數量受限」等，原有記憶就很容易失效。相比之下，如果讀者先建立起資訊組織的意識，就更容易理解這些題目之間的共通結構：它們本質上都在圍繞狀態壓縮、重複子問題消除、約束條件表達和目標函數最佳化展開。

這也是 PixelBank 這類學習計畫值得關注的地方。它沒有把基礎數學當成裝飾性前置知識，而是試圖說明：抽象理論的價值，在於幫助你更快看見問題結構。對自學者而言，這種路線很重要。因為很多人並不是缺少刷題量，而是缺少把零散知識連接起來的框架。一旦理論與實踐被打通，學習效率往往會顯著提高。你不再只是「記住零錢兌換要用動態規劃」，而是能理解為什麼暴力搜尋會製造資訊冗餘，為什麼貪心會因為局部最優而失真，為什麼狀態轉移其實是在逐步擴展一個經過壓縮的知識表。

從更大的產業背景看，這種內容也反映了技術教育敘事正在變化。過去，基礎理論常被視為學術路線的一部分，演算法題則更像求職準備工具；如今越來越多平台開始強調兩者之間的往復關係。原因很簡單：在軟體開發、資料科學、機器學習工程乃至 AI 應用開發中，真正有競爭力的人，往往不是背題最快的人，而是能在陌生問題中迅速辨認結構、抽象狀態、降低複雜度的人。資訊理論訓練的是對不確定性和表達效率的敏感度，演算法訓練的是把這種敏感度變成可執行方案的能力。兩者結合，才更接近現代技術工作中的真實要求。

當然，也需要看到這類文章的邊界。資訊理論和零錢兌換之間並不是嚴格的一一對應關係，讀者不應誤以為只要理解了熵或編碼，就能自動寫出所有動態規劃題。更合理的理解是：資訊理論提供一種元視角，幫助我們從「資訊如何被組織和復用」的角度理解演算法；而具體題解仍然需要扎實的建模訓練、邊界討論和複雜度分析。換言之，理論不會直接取代技巧，但它能讓技巧不再只是死記硬背。

如果把這篇文章放到更實際的學習路徑中，它最適合兩類讀者。第一類是剛接觸演算法、對刷題有畏難感的人。這類讀者常常會被程式碼細節淹沒，覺得動態規劃像某種神祕魔法。透過資訊理論視角切入，他們更容易明白動態規劃是在「存資訊、用資訊、避免重複資訊」。第二類是已經刷過不少題、但總覺得遷移能力不足的人。對他們來說，這種跨學科解釋有助於擺脫對題型模板的依賴，轉而形成對問題結構的更深理解。

未來如果沿著這條思路繼續展開，還可以把更多經典問題納入同一框架：背包問題可以討論資源約束下的資訊保留；編輯距離可以討論序列差異如何被最小成本編碼；最短路徑問題可以討論局部狀態如何逐步逼近全域最優；甚至在機器學習中，特徵選擇、模型壓縮、損失最佳化，也都能在某種意義上與資訊效率聯繫起來。這樣的學習路徑，比單純羅列題庫更有長期價值，因為它訓練的是一種跨問題復用的理解能力。

總體來看，這篇來自 Dev.to AI 的教學內容之所以值得收錄，不在於它給出了一個多麼罕見的演算法題，而在於它示範了一種更成熟的技術寫法：不把理論和實戰割裂，而是讓抽象概念透過具體題目落地，讓具體題目反過來驗證理論的解釋力。對於中文科技內容讀者而言，這類文章的價值正在於此——它不只是教你解一道題，而是在幫助你建立一種更穩固的技術思維框架。理解了「零錢兌換」為何能用動態規劃解決，你得到的也許不只是這道題的答案，更是面對未來複雜問題時，對資訊、狀態、約束與最優性之間關係的重新把握。