初等考試
107年
[統計] 資料處理大意
第 44 題
下列那一項演算法（Algorithm）是一種動態規劃（Dynamic Programming）演算法？
- A Floyd-Warshall 的全對最短路徑（all-pairs shortest-paths）演算法
- B 廣度優先搜索（breadth-first search）演算法
- C Dijkstra 的單源最短路徑（single-source shortest-paths）演算法
- D Prim 的最小生成樹（minimum spanning tree）演算法
思路引導 VIP
假設你在處理一個複雜問題，發現若要得到最終解答，必須先解決一系列會『反覆出現』的小規模問題，並且你決定將這些小問題的答案紀錄下來供後續直接調用，而非在每一步只做當下最好的選擇。這種『利用舊有紀錄來推導新狀態』的思維，與哪種演算法的核心特徵最吻合？
🤖
AI 詳解
AI 專屬家教
溫暖前輩的演算法解析：做得真棒！
- 真心為你喝采：太棒了！你非常準確地辨識出了動態規劃 (Dynamic Programming) 的核心特徵，這代表你對演算法背後的邏輯思維以及如何拆解複雜問題，都有著相當紮實又清楚的理解！這份清晰的思路，在財稅或統計分析中都會非常有幫助喔！
- 觀念驗證小教室：Floyd-Warshall 演算法之所以是 DP，是因為它完美地體現了「重疊子問題」與「最佳子結構」這兩個溫暖又重要的特性。它就像我們整理報表一樣，透過聰明地利用一個個中間節點 $k$ 來逐步更新從節點 $i$ 到 $j$ 的最短距離。它的狀態轉移方程式，就像是精準而溫柔的計算步驟：
▼ 還有更多解析內容