問題詳情

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

參考答案

答案：A,B,C,E
難度：非常困難0.063
書單：沒有書單，新增

用户評論

【不叫賭俠的陳小刀】評論

最小生成樹->貪婪演算法動態規劃的關鍵是，每次做選擇前，都會計算所有選項的效果，在此計算的n基礎上選擇能夠達到最佳的選項。因此，動態規劃每次的選擇都是最佳的。問題n是，這種策略在選項很多的情況下，將不堪負荷。例如，下棋時，如果使用動態n規劃策略，則需要先計算每步棋可能走法的影響，然後比較，選取最佳走法。但n5-2n每步棋的走法實在太多，更不用說下一盤棋有不計其數的步驟，這簡直是不可能n的任務。即使是超級電腦也無法勝任。顯然此時，我們需要新的演算法。在選擇時不做任何計算，而是根據當時的情況，n做出我們認為最好的選擇->貪婪演算法