前言
笔者之前也断断续续写过几篇javascript数据结构和算法的文章,之所以要写,是因为它们很重要。在前端的职业生涯中我们会遇到很多选择,走向不同的方向,但是唯一不变的,就是技术思维。...正文
笔者抽空总结了几个比较经典且实用的算法, 最少硬币找零问题 是本文介绍的第一道算法题:
问题:给出要找零的钱数amount以及可用的硬币面额c1, c2, c3, ..., 求所需的最少硬币个数。...硬币找零问题也可以用该思想来解决,首先按照正常的逻辑,我们可以先计算在给定金额amount和给定面额下,一共有几种找零方法,然后求出长度最短的找零方案。...若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。...其本质是一种近似解法,通过局部最优解来实现整体最优的目的,应用到我们的题目中,好比如下图所示的思路:
局部最优意味着每次我们都优先取最大的硬币面额,直到剩余金额不足最大金额时,我们会取第二大的面额,以此类推