本系列為labuladong的算法小抄的javascript實(shí)現(xiàn)版本，實(shí)現(xiàn)原理參考labuladong的算法小抄。
本文為第0章第2小節(jié)《動(dòng)態(tài)規(guī)劃》所涉及的代碼，直接上代碼
//斐波那契數(shù)列
/**
* @param {number} n
* @return {number}
*/
// var fib = function (n) {
// if (n < 1) return 0;
// const mp = {};
// return helper(n, mp);
// };
// var helper = function (n, mp) {
// if (n == 1 || n == 2) return 1;
// if (mp[n] != undefined) {
// return mp[n];
// }
// mp[n] = helper(n - 1, mp) + helper(n - 2, mp);
// return mp[n];
// };
var fib = function (n) {
if (n < 1) return 0;
if (n == 2 || n == 1) return 1;
let prev = 1;
let curr = 1;
for (let i = 2; i < n; i++) {
let sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
};
// console.log(fib(3));
/**
* 湊零錢問(wèn)題v1.0 暴力窮舉
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
function dp(n) {
if (n == 0) return 0;
if (n < 0) return -1;
let res = Infinity;
for (let index in coins) {
let sb = dp(n - coins[index]);
if (sb == -1) continue;
res = Math.min(res, 1 + sb);
}
return res;
}
let num = dp(amount);
return num == Infinity ? -1 : num;
};
// /**
// * 湊零錢問(wèn)題v2.0 備忘錄
// * @param {number[]} coins
// * @param {number} amount
// * @return {number}
// */
// var coinChange = function (coins, amount) {
// let mp = {};
// function dp(n) {
// if (mp[n]) return mp[n];
// if (n == 0) return 0;
// if (n < 0) return -1;
// let res = Infinity;
// for (let index in coins) {
// let sb = dp(n - coins[index]);
// if (sb == -1) continue;
// res = Math.min(res, 1 + sb);
// }
// if (res != Infinity) {
// mp[n] = res;
// } else {
// mp[n] = -1;
// }
// return res;
// }
// let num = dp(amount);
// return num == Infinity ? -1 : num;
// };
/**
* 湊零錢問(wèn)題v2.0 備忘錄
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
let infos = new Array(amount + 1);
infos.fill(amount + 1);
infos[0] = 0;
for (let i = 0; i < infos.length; i++) {
for (let index in coins) {
if (i - coins[index] < 0) continue;
infos[i] = Math.min(infos[i], 1 + infos[i - coins[index]]);
}
}
return infos[amount] == amount + 1 ? -1 : infos[amount];
};
console.log(coinChange([1, 2, 5], 11));
