[TOC] # 簡介 動態規劃（Dynamic Programming，DP)是一種將復雜問題分解成更小的子問題來解決的優化技術。 <br> 要注意動態規劃和分而治之（歸并排序和快速排序算法中用到的那種）是不同的方法。分而治之方法是把問題分解成相互獨立的子問題，然后組合它們的答案，而動態規劃則是將問題分解成相互依賴的子問題。 另一個例子是上一節解決的斐波那契問題。我們將斐波那契問題分解成如該節圖示的小問題。 <br> <br> # 步驟 用動態規劃解決問題時，要遵循三個重要步驟： 1. 定義子問題 2. 實現要反復執行而解決子問題的部分（可能是遞歸） 3. 識別并求解出邊界條件 <br> <br> # 分類 能用動態規劃解決的一些著名的問題如下： * 背包問題：給出一組項目，各自有值和容量，目標是找出總值最大的項目的集合。這個 問題的限制是，總容量必須小于等于“背包”的容量 * 最長公共子序列：找出一組序列的最長公共子序列（可由另一序列刪除元素但不改變余 下元素的順序而得到） * 矩陣鏈相乘：給出一系列矩陣，目標是找到這些矩陣相乘的最高效辦法（計算次數盡可能少)，相乘操作不會進行，解決方案是找到這些矩陣各自相乘的順序 * 硬幣找零：給出面額為 d1...dn 的一定數量的硬幣和要找零的錢數，找出有多少種找零的方法 * 圖的全源最短路徑：對所有頂點對(u, v)，找出從頂點u到頂點v的最短路徑。 <br> <br> # 最少硬幣找零 最少硬幣找零問題是硬幣找零問題的一個變種。硬幣找零問題是給出要找零的錢數，以及可 用的硬幣面額 d1...dn 及其數量，找出有多少種找零方法。最少硬幣找零問題是給出要找零的錢數， 以及可用的硬幣面額 d1...dn 及其數量，找到所需的最少的硬幣個數。 <br> 例如，美國有以下面額(硬幣）：d1=1, d2=5, d3=10, d4=25，如果要找36美分的零錢，我們可以用1個25美分、1個10美分和1個便士（ 1美分)。 <br> 最少硬幣找零的解決方案是找到 n 所需的最小硬幣數。但要做到這一點，首先得找到對每個 x < n 的解。然后，我們將解建立在更小的值的解的基礎上。 <br> 來看看算法： ~~~ class MinCoinChange { constructor(coins) { this.coins = coins this.cache = {} } makeChange(amount) { if (!amount) return [] if (this.cache[amount]) return this.cache[amount] let min = [], newMin, newAmount this.coins.forEach(coin => { newAmount = amount - coin if (newAmount >= 0) { newMin = this.makeChange(newAmount) } if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) { min = [coin].concat(newMin) } }) return (this.cache[amount] = min) } } ~~~ <br> 測試一下算法： ~~~ const minCoinChange = new MinCoinChange([1, 5, 10, 25]) console.log(minCoinChange.makeChange(36)) // [1, 10, 25] const minCoinChange2 = new MinCoinChange([1, 3, 4]) console.log(minCoinChange2.makeChange(6)) // [3, 3]復制代碼 ~~~ 所以，找零錢數為6時，最佳答案是兩枚價值為3的硬幣