摘自《javascript数据结构与算法第二版》
斐波那契数列
- 1 和 2 的斐波那契数是 1；
- n（n>2）的斐波那契数是 (n - 1) 的斐波那契数加上 (n - 2) 的斐波那契数。
递归版
function fibonacci(num) {
if(num === 1 || num === 2) {
return 1
}
return fibonacci(num - 1) + fibonacci(num - 2)
}
非递归版
function fibonacci(n) {
if(n === 0) {
return 0
}
if(n === 1) {
return 1
}
let fn1 = 0
let fn2 = 1
let target = 0
for(let i = 2; i <= n; i++) {
target = fn1 + fn2
fn1 = fn2
fn2 = target
}
return target
}
动态规划
动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。
用动态规划解决问题时，要遵循三个重要步骤：
- 定义子问题；
- 实现要反复执行而解决子问题的部分（这一步要参考前一节讨论的递归的步骤）；
- 识别并求解出边界条件。
动态规划和分而治之（归并排序和快速排序算法中用到的那种）是不同的方法。分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则是将问题分解成相互依赖的子问题。
最少硬币找零问题
最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可用的硬币面额d 1 …d n 及其数量，找出有多少种找零方法。最少硬币找零问题是给出要找零的钱数，以及可用的硬币面额d 1 …d n 及其数量，找到所需的最少的硬币个数。
例如，美国有以下面额（硬币）：d 1 =1，d 2 =5，d 3 =10，d 4 =25。
如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（1美分）。
function MinCoinChange(coinsValue) {
let coins = coinsValue //{1}
let cache = {} //{2}
this.makeChange = function (amount) {
let me = this
if (!amount) { //{3}
return []
}
if (cache[amount]) { //{4}
return cache[amount]
}
let min = [], newMin, newAmount
for (let i = 0; i < coins.length; i++) { //{5}
let coin = coins[i]
newAmount = amount - coin //{6}
if (newAmount >= 0) {
newMin = me.makeChange(newAmount) //{7}
}
if (
newAmount >= 0 && //{8}
(newMin.length < min.length - 1 || !min.length)//{9}
&& (newMin.length || !newAmount) //{10}
) {
min = [coin].concat(newMin) //{11}
console.log('new Min ' + min + ' for ' + amount)
}
}
return (cache[amount] = min) //{12}
}
}
let minCoinChange = new MinCoinChange([1, 5, 10, 25])
console.log(minCoinChange.makeChange(36))
MinCoinChange类接收coins参数（行 {1}），代表问题中的面额。对美国的硬币系统而言，它是 [1, 5, 10, 25] 。我们可以随心所欲传递任何面额。此外，为了更加高效且不重复计算值，我们使用了 cache（行 {2}）。
接下来是makeChange 方法，它也是一个递归函数，找零问题由它解决。首先，若 amount不为正（< 0），就返回空数组（行 {3}）；方法执行结束后，会返回一个数组，包含用来找零的各个面额的硬币数量（最少硬币数）。
接着，检查cache缓存。若结果已缓存（行 {4}），则直接返回结果；否则，执行算法。我们基于coins参数（面额）解决问题。因此，对每个面额（行 {5}），我们都计算 newAmount（行 {6} ）的值，它的值会一直减小，直到能找零的最小钱数（别忘了本算法对所有的x < amount 都会计算makeChange结果）。若 newAmount是合理的值（正值），我们也会计算它的找零结果（行{7}）。
最后，我们判断 newAmount是否有效， minValue （最少硬币数）是否是最优解，与此同时 minValue 和newAmount是否是合理的值（{ 行 10}）。若以上判断都成立，意味着有一个比之前更优的答案（行 {11}，以5美分为例，可以给5便士或者1个5美分镍币，1个5美分镍币是最优解）。最后，返回最终结果（行 {12}）。
贪心算法求解
贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。它不像动态规划那样计算更大的格局。
function MinCoinChange(coins) {
let coinArr = coins
this.makeChange = function (amount) {
let change = []
let total = 0
for (let i = coinArr.length; i >= 0; i--) {
let coin = coinArr[i]
while (total + coin <= amount) {
change.push(coin)
total += coin
}
}
}
}
const minCoinChange = new MinCoinChange([1, 5, 10, 25])
console.log(minCoinChange.makeChange(36))
结果依然是 [25, 10, 1] ，和用DP得到的一样。下图阐释了算法的执行过程：
然而，如果用 [1, 3, 4] 面额执行贪心算法，会得到结果 [4, 1, 1] 。如果用动态规划的解法，会得到最优的结果 [3, 3] 。
网友评论