javascript经典算法之最小硬币找零问题

前言

笔者之前也断断续续写过几篇javascript数据结构和算法的文章,之所以要写,是因为它们很重要。在前端的职业生涯中我们会遇到很多选择,走向不同的方向,但是唯一不变的,就是技术思维。

而算法,正是技术思维应用的结晶。对于初中级工程师，实现业务是我们的首要职责，没有太多的时间和精力关注代码性能和执行效率，往往能用即可。这种状态无非对错，毕竟在不同阶段侧重点不同，业务能力往往是一个工程师进阶的必经之路，但是往长远来看，维持这种状态非常不利于自身的长远发展，因为长期处于业务优先的状态容易让人产生思维惰性，不愿意尝试更优方案，所以最后的结果就是忙了很多年，能力却没有提升多少，最终会被新生代淘汰。

笔者在刚从事前端工作的时候也认为算法对于前端，意义不大。天真的以为前端就是写写页面，调调接口，没有任何难度。但是越往后研究,随着公司对用户体验的要求越来越高，以及对前端业务逻辑的日渐复杂，之前的"算法无用论"不断受到了挑战，最后为了改变已有的格局，笔者慢慢开始研究设计模式和算法，刚开始可能比较吃力，但是坚持下去，不断的理解和应用，大大提高了笔者解决问题的能力，并且也逐渐挑起了公司前端的大梁.。所以作为一个过来人，笔者希望大家也逐渐对算法这块重视起来，毕竟如果想进大厂或者自己心仪的公司，学习算法是你的必经之路。

正文

笔者抽空总结了几个比较经典且实用的算法, 最少硬币找零问题 是本文介绍的第一道算法题:

问题：给出要找零的钱数amount以及可用的硬币面额c1, c2, c3, ..., 求所需的最少硬币个数。

思考这道问题可以有很多不同的思路, 笔者主要采用两种方法来解决这个问题:

1. 动态规划法 2. 贪心算法 接下来笔者具体介绍这两种算法的思路和实现代码.

1. 动态规划法

动态规划的思想是把一个复杂问题分解为多个子问题，通过解决一个个子问题，再把子问题合并比较，从而解决复杂问题的思想。

硬币找零问题也可以用该思想来解决，首先按照正常的逻辑，我们可以先计算在给定金额amount和给定面额下，一共有几种找零方法，然后求出长度最短的找零方案。当我们使用动态规划来解决该问题时，我们可以将其分解成几个子方案，最终通过条件判断最优方案，具体实现代码如下：

// 硬币找零算法
function MinCoinChange(coins) {
  let cache = {}

  this.makeChange = function(amount) {
    let me = this;
    if(!amount) {
      return []
    }
    if(cache[amount]) {
      return cache[amount]
    }
    let min = [], newMin, newAmount;
    for(let i=0, len = coins.length; i<len; i++){
      let coin = coins[i];
      newAmount = amount - coin;
      if(newAmount >= 0) {
        newMin = me.makeChange(newAmount);
      }
      if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
        min = [coin].concat(newMin);
      }
    }
    return (cache[amount] = min)
  }
}

2. 贪心算法

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

其本质是一种近似解法，通过局部最优解来实现整体最优的目的，应用到我们的题目中，好比如下图所示的思路：

局部最优意味着每次我们都优先取最大的硬币面额，直到剩余金额不足最大金额时，我们会取第二大的面额，以此类推，从而实现总硬币数最小的目的。其思想非常简单，我们直接上代码：

// 最少硬币找零 - 贪心算法
function MinCoinChange1(coins) {
  return function(amount) {
    let total = 0, change = []
    for(let i= coins.length; i>=0; i--) {
      let coin = coins[i]
      while(total + coin <= amount) {
        change.push(coin)
        total += coin
      }
    }
    return change
  }
}

以上就是两种算法的实现，大家也可以想想其他的解决方案，欢迎一起交流讨论。

最后

为了巩固算法知识,笔者定了一个2个月的小目标, 2个月里每周总结一道算法题及其解法, 希望以此来提高自己以及大家在实际工作中的算法应用.

同时笔者每周会总结1-2篇企业中实用的工程化技术总结, 内容包括小程序, H5开发, 数据可视化,前端工程化/组件化等实战知识,如果疑问,欢迎和笔者交流~