試題詳解

13.以下哪些問題通常使用動態程式規劃(DynamicProgramming)來解決？
(A)最長共同子序列（LongestCommonSubsequence）：在兩個序列中找到一個最長的 子序列，該子序列在兩個序列中以相同的順序出現
(B)最小編輯距離（MinimumEditDistance）：計算將一個字串轉換成另一個字串所需的 最小編輯次數。
(C)最長遞增子序列（LongestIncreasingSubsequence）：在一個數列中找到一個最長的 遞增子序列。
(D)最小生成樹（MinimumSpanningTree）：在一個連通的帶權無向圖中，找到一棵包 含所有節點的樹，且所有邊的權值總和最小。
(E)最短路徑問題（ShortestPathProblem）：在一個帶權有向圖中，找到從一個起點到其 他所有節點的最短路徑。