# Chapter-4 Dynamic Programming # 第4章 動態規劃 -------- 1. LinearDP 線性動態規劃 1. [LongestCommonSubsequence 最長公共子序列](LinearDP/LongestCommonSubsequence/) 2. [LongestIncreasingSubsequence 最長遞增子序列](LinearDP/LongestIncreasingSubsequence/) 3. [LongestIncreasingSubsequenceExtension 最長遞增子序列擴展](LinearDP/LongestIncreasingSubsequenceExtension/) 4. [BidirectionalSubsequence 雙向子序列](LinearDP/BidirectionalSubsequence/) 2. BagDP 背包問題 1. [ZeroOneBag 01背包](BagDP/ZeroOneBag/) 2. [CompleteBag 完全背包](BagDP/CompleteBag/) 3. [TwoDimensionBag 二維背包](BagDP/TwoDimensionBag/) 4. [GroupBag 分組背包](BagDP/GroupBag/) 3. RegionalDP 區域動態規劃 1. [MinimumMergeCost 最小合并代價](RegionalDP/MinimumMergeCost/) 2. [MinimumMergeCostExtension 最小合并代價擴展](RegionalDP/MinimumMergeCostExtension/) 3. [MaximumBinaryTreeMerge 最大二叉樹合并](RegionalDP/MaximumBinaryTreeMerge/) 4. TreeDP 樹形動態規劃 1. [BinaryTreeDP 二叉樹動規](TreeDP/BinaryTreeDP/) 2. [MultipleTreeDP 多叉樹動規](TreeDP/MultipleTreeDP/) 3. [MultipleTreeDPExtension 多叉樹動規問題擴展](TreeDP/MultipleTreeDPExtension/) 4. [LoopedMultipleTreeDP 帶環多叉樹動規](TreeDP/LoopedMultipleTreeDP/) 5. [TraverseBinaryTreeDP 遍歷二叉樹動規](TreeDP/TraverseBinaryTreeDP/) -------- #### 動態規劃 動態規劃（Dynamic Programming）是運籌學（線性規劃、網絡流也屬于運籌學）中的一個問題分支，用于求解最優解。Dynamic Programming將一個復雜的問題拆分為多個階段的決策，決策函數用$$ f $$表示。基本特性如下： $$ (1) $$ 每個決策所做的計算都只針對當前階段； $$ (2) $$ 當前階段僅僅依賴于上一階段，與再前面的階段無關； $$ (3) $$ 當前階段的決策為未來決策做出一個 動態規劃一般使用遞歸公式求解。遞歸公式也稱作狀態轉移方程。 最優性原則：對以后階段所做出的未來決策會產生一個最優策略，它與前面各階段所采用的策略無關。 本書中我們將動態規劃問題分為$$ 4 $$個部分： $$ (1) $$ 線性DP； $$ (2) $$ 背包問題； $$ (3) $$ 區域DP； $$ (4) $$ 樹型DP； -------- #### 運籌學 * https://en.wikipedia.org/wiki/Operations_research * https://book.douban.com/subject/4747771/