贪心算法和动态规划
贪心算法和动态规划
贪心算法
当遇到一个求解全局最优解问题时，如果可以将全局问题切分为小的局部问题，并寻求局部最优解，同时可以证明局部最优解累计的结果就是全局最优解，则可以使用贪心算法
找零问题：
示例：假设你有一间小店，需要找给客户 46 分钱的硬币，你的货柜里只有面额为 25 分、10 分、5 分、1 分的硬币，如何找零才能保证数额正确并且硬币数最小
JavaScript 代码：
/**
* 得到一个找零的结果： [25, 10, 10, 1]
* @param {*} total 要找零的总额
* @param {*} denos 拥有的面额
*/
function exchange(total, denos) {
if (total <= 0) {
return [] //不用找零
}
// 寻找最大的面额，同时要保证面额小于等于total
var max = 0
for (var i = 0; i < denos.length; i++) {
var deno = denos[i]
if (deno > max && deno <= total) {
max = deno
}
}
// max记录这一次的解（局部最优解）
var result = [max]
var next = exchange(total - max, denos) //得到后续的局部最优解
result = result.concat(next) //拼接之后，就是整体最优解
return result
}
// 要找的总金额
var total = 51
// 拥有的面值
var denos = [30, 25, 10, 5, 1]
var result = exchange(total, denos)
console.log(result) // [25, 10, 10, 1]
动态规划
分治法有一个问题，就是容易重复计算已经计算过的值，使用动态规划，可以将每一次分治时算出的值记录下来，防止重复计算，从而提高效率。
青蛙跳台阶问题：
有 N 级台阶，一只青蛙每次可以跳 1 级或两级，一共有多少种跳法可以跳完台阶？
Js 代码：
var num1 = 0
// 不使用动态规划
function count1(total) {
num1++
if (total === 0) return 0
if (total === 1) return 1
if (total === 2) return 2
return count1(total - 1) + count1(total - 2)
}
var num2 = 0
//使用动态规划优化效率
function count2(total) {
var cache = {} //缓存已经计算过的结果
function _count(total) {
if (cache[total] !== undefined) {
return cache[total] //直接使用缓存结果
}
num2++
var result
if (total === 0) result = 0
else if (total === 1) result = 1
else if (total === 2) result = 2
else {
result = _count(total - 1) + _count(total - 2)
}
cache[total] = result
return result
}
return _count(total)
}
console.time('没有动态规划')
var result1 = count1(25)
console.log(result1, '计算了' + num1 + '次')
console.timeEnd('没有动态规划')
console.time('动态规划')
var result2 = count2(25)
console.log(result2, '计算了' + num2 + '次')
console.timeEnd('动态规划')
// 121393 "计算了150049次"
// 没有动态规划: 5.377197265625ms
// 121393 "计算了25次"
// 动态规划: 0.339111328125ms
由上述代码运行的结果可知，动态规划可以大大的提高程序的效率
