20 | 算法思想：JS中分治、贪心、回溯和动态规划

石川

你好，我是石川。
在算法中，我们提到如递归、分治、贪心、回溯和动态规划这些不同的算法思想时一般会分开来说。但实际上，它们之间是有着关联的。比如递归和回溯可以解决贪心顾及不到或者不能重试的问题。而动态规划又可以在利用递推公式的基础上解决递归中的一些短板。
能够比较好贯穿整个思想的是一个硬币找零的例子，即在几种不同面值硬币中，如何用最少的硬币数量来找零的问题。
贪心和递归分治首先，我们来看下贪心算法如何解这个题。找零问题的核心是在几种不同面值如 1、5、10 分的硬币中，用最少的枚数凑出针一个需要找零的钱数。解决这个问题最简单的办法就是使用贪心（greedy）算法，它的核心逻辑是我们先选择面值较大的来找，再逐渐选小面额的。为什么这里是从大到小，而不是从小到大呢？因为通常面值越大，用到的数量就越少。
function minCoinChange(coins, amount) {
  var change = [];
  var total = 0;
  for (let i = coins.length; i >= 0; i--) { // 从大到小循环
    var coin = coins[i];
    while (total + coin <= amount) { // 将硬币逐个加入，面值要小于商品价格
      change.push(coin);  // 将硬币加入到结果
      total += coin; // 将硬币累加到总数
    }
  }
  return change;
}

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

JavaScript中的算法思想包括贪心、递归、分治、回溯和动态规划，它们相互关联并在解决问题时发挥重要作用。本文通过讨论硬币找零问题，深入探讨了这些算法思想之间的关联。首先介绍了贪心算法的简单易懂性及其局限性，随后讨论了递归和分治算法以及回溯和记忆函数的应用，解决了贪心算法的问题。接着引入了动态规划，通过状态转移方程和迭代循环的方式提高了执行效率。文章通过具体的例子和代码演示，生动地展现了这些算法思想的应用和优劣势。此外，还延伸讨论了位运算在JavaScript中的使用和思想，以及位运算对加减乘除等计算的效率提升。最后，总结了算法思想在不同领域的应用，并提出了思考题，鼓励读者进行交流讨论。整体而言，本文深入浅出地介绍了算法思想及其在实际问题中的应用，对读者深入理解算法思想提供了有益的参考。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《JavaScript 进阶实战课》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(4)

最新
精选

静心
表格中非和异或的解释好像反了
作者回复: 谢谢指正！已经修改了。
2022-11-23归属地：海南


趙學躍
-9>>>1 = 2147483643 9>>>1 = 4
2022-11-07归属地：北京

1
无咎
位移的部分，最后应该是-9 >>> 1 ``` > (9).toString(2).padStart(32, '0'); '00000000000000000000000000001001' > (9 << 1).toString(2).padStart(32, '0'); '00000000000000000000000000010010' > (9 >> 1).toString(2).padStart(32, '0'); '00000000000000000000000000000100' > (-9 >>> 1).toString(2).padStart(32, '0'); '01111111111111111111111111111011' ```
2023-05-06归属地：北京


神佑小鹿
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 // 9 >> 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 // 9 >>> 1 这个地方是不是哪里不对？？9 这个
2023-03-23归属地：广东



收起评论