動態規劃壹般可分為線性動規,區域動規,樹形動規,背包動規四類。
舉例:
線性動規:攔截導彈,合唱隊形,挖地雷,建學校,劍客決鬥等;
區域動規:石子合並, 加分二叉樹,統計單詞個數,炮兵布陣等;
樹形動規:貪吃的九頭龍,二分查找樹,聚會的歡樂,數字三角形等;
背包問題:01背包問題,完全背包問題,分組背包問題,二維背包,裝箱問題,
動態規劃問世以來,在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題,但是壹些與時間無關的靜態規劃(如線性規劃、非線性規劃),只要人為地引進時間因素,把它視為多階段決策過程,也可以用動態規劃方法方便地求解。
動態規劃程序設計是對解最優化問題的壹種途徑、壹種方法,而不是壹種特殊算法。不像搜索或數值計算那樣,具有壹個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對壹種最優化問題,由於各種問題的性質不同,確定最優解的條件也互不相同,因而動態規劃的設計方法對不同的問題,有各具特色的解題方法,而不存在壹種萬能的動態規劃算法,可以解決各類最優化問題。因此讀者在學習時,除了要對基本概念和方法正確理解外,必須具體問題具體分析處理,以豐富的想象力去建立模型,用創造性的技巧去求解。我們也可以通過對若幹有代表性的問題的動態規劃算法進行分析、討論,逐漸學會並掌握這壹設計方法。