Dynamic Programming
DP概念
將重複的子問題用表格記錄起來，節省重複計算子問題的時間。簡單來說就是以空間換取時間。求解的時候不像是Divide and Conquer那樣從原問題開始切割，而是由下而上先算出所有可能會遇到的子問題，然後再由這些子問題求出原本問題的解。
使用DP解題時我們最關心的是「DP元素」和「遞迴式」，DP元素就是表格上每一格儲存的東西所代表的意義；遞迴式表示以子問題表示所求問題答案的方法。這兩個東西決定了DP演算法的好壞。
什麼題目適合用DP解
通常DP問題只能解決 (1)處理數值範圍較小 (2)子問題重複率高 的問題。某些題目用DP方法只能讓複雜度從階乘降至指數級，輸入數值一但增大還是沒有辦法有效處理，例如旅行售貨員問題(Traveling Salesman Problem)。或者有些題目根本不需要重複解同一個子問題，此時用暴力搜尋或另尋解法可能還比較快找到解。不過不必擔心，大部分的題目只要有辦法想的到DP解，通常效率都會是很不錯的。