读【数据结构与算法】之高级算法
高级算法，本部分只包含两个主题：动态规划和贪心算法。
动态规划有时会被认为是一种与递归相反的技术。动态规划是从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体的解决方案。
贪心算法是一种寻找“优质解”为手段而达成的整体解决方案算法。这些优质的解决方案称为局部最优解，将有希望得到正确的最终解决方案，也称为全局最优解。
动态规划
动态规划实例：计算斐波那契数列
利用递归实现的方式：
/**
* 计算斐波那契数列（递归实现）
* @param {Number} n 指定序号
* @return {Number} 指定序号的值
*/
function recurFib(n) {
if (n < 2) {
return n;
} else {
return recurFib(n - 1) + recurFib(n - 2);
}
}
但是，你会发现这样的话效率会比较底下，因为每次计算都需要重新计算下之前已经计算过的值。如果把之前计算的值保存起来的话，就会得到很大提升。
使用动态规划设计算法是从他能够解决的最简单的子问题开始，继而通过得到解来解决其他更复杂的子问题。所有的子问题的解通常被存储在一个数组中以便于访问。
下边是优化后两个版本：
/**
* 计算斐波那契数列（动态规划实现-数组）
* @param {Number} n 指定序号
* @return {Number} 指定序号的值
*/
function dynFib(n) {
var val = [], i = 0;
for ( ; i <= n; i++) {
val[i] = 0;
}
if (n === 1 || n === 2) {
return 1;
} else {
val[1] = 1;
val[2] = 2;
for (i = 3; i <= n; i++) {
val[i] = val[i - 1] + val[i - 2];
}
return val[n - 1];
}
}
/**
* 计算斐波那契数列（动态规划实现-整数）
* @param {Number} n 指定序号
* @return {Number} 指定序号的值
*/
function iterFib(n) {
var last = 1, nextLast = 1,
result = 1, i = 2;
for ( ; i < n; i++) {
result = last + nextLast;
nextLast = last;
last = result;
}
return result;
}
寻找最长公共子串
使用动态规划来解决寻找最长公共子串是很适合的。该算法使用一个二维数组存储两个字符串相同位置的字符比较结果，初始化时，该数组的每一个元素设置为0，每次在这两个数组相同位置发现了匹配，就将数组对应的行和列元素加1，否则还为0。
基本实现：
/**
* 寻找最长公共子串
* @param {String} word1 单词1
* @param {String} word2 单词2
* @return {String} 单词1和单词2中最长公共子串
*/
function lcs(word1, word2) {
var max = 0, // 出现公共字符的最大长度
index = 0, // 出现最大长度时在word1中位置（从1开始计）
len1 = word1.length,
len2 = word2.length,
lcsarr = new Array(len1 + 1),
i = 0, j, ret = '';
// 初始化二维数组每一个值都为0
for ( ; i <= len1 + 1; i++) {
lcsarr[i] = new Array(len2 + 1);
for (j = 0; j <= len2 + 1; j++) {
lcsarr[i][j] = 0;
}
}
// 循环遍历所有的字母
// 如果字母相等，那么对应的长度就是
// 单词1和单词2上一个位置上所对应的
// 长度值加1，否则就是当前的两个单词
// 对应位置上的值不相等，长度值为0
for (i = 0; i <= len1; i++) {
for (j = 0; j <= len2; j++) {
if (i === 0 || j === 0) {
lcsarr[i][j] = 0;
} else {
if (word1[i - 1] === word2[j - 1]) {
lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
} else {
lcsarr[i][j] = 0;
}
}
// 如果出现了新的最长长度
// 那么就对max重新赋值
// 将index也重新赋值
if (max < lcsarr[i][j]) {
max = lcsarr[i][j];
index = i;
}
}
}
if (max === 0) {
ret = '';
} else {
// 从index - max的位置开始 取得单词2中
// 到max长度位置的所有字母加起来就是
// 需要的结果
for (i = index - max; i <= max; i++) {
ret += word2[i];
}
}
return ret;
}
背包问题
经典背包问题：假如你是一个保险箱大盗，打开了一个满是宝物的保险箱，但是你必须挑选一些价值最高的东西放到你拿的小背包中，该怎么选择？
经典实现是使用递归来实现：
/**
* 背包问题（递归）
* @param {Number} capacity 体积
* @param {Array} size 尺寸组成数组
* @param {Array} value 价值组成的数组
* @param {Number} n 当前用于计算长度
* @return {Number} 最大价值
*/
function knapsack(capacity, size, value, n) {
if (n === 0 || capacity === 0) return 0;
if (size[n - 1] > capacity) {
return knapsack(capacity, size, value, n - 1);
} else {
return Math.max(
value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1));
}
}
下边看看利用动态规划来实现这个背包问题：
/**
* 背包问题（动态规划）
* @param {Number} capacity 体积
* @param {Array} size 尺寸组成数组
* @param {Array} value 价值组成的数组
* @param {Number} n 当前用于计算长度
* @return {Number} 最大价值
*/
function dKnapsack(capacity, size, value, n) {
var K = [], i = 0, w = 0;
for ( ; i <= capacity + 1; i++) {
K[i] = [];
}
for (i = 0; i <= n; i++) {
for (w = 0; w <= capacity; w++) {
if (i === 0 || w === 0) {
K[i][w] = 0;
} else if (size[i - 1] <= w) {
K[i][w] = Math.max(value[i - 1] + K[i - 1][w - size[i - 1]], K[i - 1][w]);
} else {
K[i][w] = K[i - 1][w];
}
}
}
return K[n][capacity];
}
贪心算法
贪心算法就是一种比较简单的算法，他总是会选择当下的最优解，而不去考虑这一次选择会不会对未来的选择造成什么影响。
贪心算法案例：找零问题
从商店里买了一些商品，找零63美分，店员要怎么样给你找零呢？根据贪心算法他会给你两个25美分一个10美分和三个1美分。当然，这是在没有使用50美分的情况下。
基本实现：
/**
* 找零
* @param {Number} origAmt 总钱数
* @return {Array} 需要找的不同面额钱个（张）数
*/
function makeChange(origAmt) {
var remainAmt = 0;
// 不同面额钱 25美分 10美分 5美分 1美分
var money = [.25, .1, .05, .01];
var i = 0, len = money.length;
var ret = [], tmp;
for ( ; i < len; i++) {
if (origAmt === 0) break;
tmp = money[i];
// 按顺序 由小到大
if (origAmt % tmp < origAmt) {
ret[i] = parseInt(origAmt / tmp);
origAmt = remainAmt = origAmt % tmp;
}
}
return ret;
}
具体运行例子请看demo高级算法