# 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/
- Content 目錄
- Preface 前言
- Chapter-1 Sort 第1章 排序
- InsertSort 插入排序
- BubbleSort 冒泡排序
- QuickSort 快速排序
- MergeSort 歸并排序
- Chapter-2 Search 第2章 搜索
- BinarySearch 二分查找法(折半查找法)
- BruteForce 暴力枚舉
- Recursion 遞歸
- BreadthFirstSearch 廣度優先搜索
- BidirectionalBreadthSearch 雙向廣度搜索
- AStarSearch A*搜索
- DancingLink 舞蹈鏈
- Chapter-3 DataStructure 第3章 數據結構
- DisjointSet 并查集
- PrefixTree(TrieTree) 前綴樹
- LeftistTree(LeftistHeap) 左偏樹(左偏堆)
- SegmentTree 線段樹
- FenwickTree(BinaryIndexedTree) 樹狀數組
- BinarySearchTree 二叉查找樹
- AVLTree AVL平衡樹
- RedBlackTree 紅黑樹
- Chapter-4 DynamicProgramming 第4章 動態規劃
- Chapter-5 GraphTheory 第5章 圖論
- Chapter-6 Calculation 第6章 計算
- LargeNumber 大數字
- Exponentiation 求冪運算
- Chapter-7 CombinatorialMathematics 第7章 組合數學
- FullPermutation 全排列
- UniqueFullPermutation 唯一的全排列
- Combination 組合
- DuplicableCombination (元素)可重復的組合
- Subset 子集
- UniqueSubset 唯一的子集
- Permutation 排列
- PermutationGroup 置換群
- Catalan 卡特蘭數
- Chapter-8 NumberTheory 第8章 數論
- Sieve 篩選算法
- Euclid 歐幾里得
- EuclidExtension 歐幾里得擴展
- ModularLinearEquation 模線性方程
- ChineseRemainerTheorem 中國剩余定理
- ModularExponentiation 模冪運算
- Chapter-9 LinearAlgebra 第9章 線性代數
- Chapter-10 AnalyticGeometry 第10章 解析幾何
- Chapter-11 TextMatch 第11章 文本匹配
- SimpleMatch 簡單匹配
- AhoCorasickAutomata AC自動機
- KnuthMorrisPratt KMP匹配算法
- RabinKarp RabinKarp算法
- BoyerMoore BoyerMoore算法
- Chapter-12 GameTheory 第12章 博弈論
- BashGame 巴什博弈
- WythoffGame 威佐夫博弈
- NimGame 尼姆博弈