算法设计与技巧

分而治之

将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将解决方式合并以解决原来的问题。

分而治之算法可以分为三个部分：

  1. 分解原问题为多个子问题。
  2. 解决子问题，用返回解决子问题的方式递归算法。
  3. 组合这些子问题的解决方式，得到原问题的解。

二分搜索分而治之实现

分解：计算mid并搜索数组较小或较大的一半。

解决：在较小或较大的一半中搜索值。

合并：这步不需要，因为直接返回了索引值。

  1. function binarySearchRecursive(array, value, low, hign) {
  2.     if(low <= hign) {
  3.         const mid = Math.floor((low + hign)/2);
  4.         const element = array[mid];
  5.         if(element < value) {
  6.             return binarySearchRecursive(array, value, mid+1,hign);
  7.         } else if(eleemnt > value) {
  8.             return binarySearchRecursive(array, value, low, mid - 1);
  9.         } else {
  10.             return mid;
  11.         }
  12.     }
  13.     return DOES_NOT_EXIST;
  14. }
  16. export function binarySearch(array, value) {
  17.     const sortedArray = quickSort(array);
  18.     const low = 0;
  19.     const hign = sortedArray.length - 1;
  21.     return binarySearchRecursive(array, value, low, hign);
  22. }

动态规划

是一种将复杂问题分解成更小的子问题来解决的优化技术。

分而治之是把问题分解成相互独立的子问题，然后组合他们的答案；动态规划是将问题分解成相互依赖的子问题。

解决问题时要遵循三个步骤：

  1. 定义子问题；
  2. 实现要反复执行来解决子问题的部分；
  3. 识别并求解出基线条件。

能用动态规划解决的一些著名问题如下：

  • 背包问题：给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于背包的容量。
  • 最长公共子序列：找出一组序列的最长公共子序列。
  • 矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法。相乘运算不会进行，解决方式是找到这些矩阵各自相乘的顺序。
  • 硬币找零：给出面额d1~dn的一定数量的硬币和要找零的钱数，找出有多少种找零的办法。
  • 图的全源最短路径：对所有顶点对(u,v)，找出最短路径。

最少硬币找零问题

该问题是硬币找零问题的一种。硬币找零问题是给出要找零的钱数，以及可用的硬币面额d1，。。。，dn及其数量，找出共有多少种找零方法。最少硬币找零问题是给出要找零的钱数以及可用的硬币面额d1，。。。，dn及其数量，找到所需的最少的硬币个数。

例如，d1=1，d2=5，d3=10，d4=25。如果要找36的零钱。可以用一个25，一个10，一个一。如何将这个解答转化成算法？

最少硬币找零的解决方案是找到n所需的最小硬币数。但要做到这一点，首先要找到对每个x<n的解。然后，可以基于更小的值的解来求解。

  1. function minCoinChange(coins, amount) {
  2.     const cache = [];     
  3.     const makeChange = (value) => {
  4.         if (!value) {
  5.             return [];
  6.         }
  7.         if (cache[value]) {
  8.             return cache[value];
  9.         }
  10.         let min = [];
  11.         let newMin;
  12.         let newAmount;
  13.         for (let i = 0; i < coins.length; i++) {
  14.             const coin = coins[i];
  15.             newAmount = value - coin;
  16.             if (newAmount >= 0) {
  17.                 newMin = makeChange(newAmount);
  18.             }
  19.             if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length)
  20.                 && (newMin.length || !newAmount)) {
  21.                 min = [coin].concat(newMin);
  22.                 console.log('new Min' + min + ' for ' + newAmount);
  23.             }
  24.         }
  25.         return (cache[value] = min);
  26.     };
  27.     return makeChange(amount);
  28. }

minCoinChange参数接收coins参数，代表问题中的面额（[1,5,10,25]）。可以传递任何面额。此外，为了更高效且不重复计算值，我们使用了cache。

makeChange方法是一个递归函数，用来解决问题。在27行被调用，amount作为参数传入，它是内部函数，所以也能访问cache变量。

首先，若amount不为正就返回空数组；方法执行结束后会返回一个数组，包含用来找零的各个面额的硬币数量（最少硬币数）。接着检查cache缓存。若结果已缓存则直接返回结果（行8），否则执行算法。

基于coins参数解决问题，对每个面额都计算newAmount的值，它的值会一直减小，直到能找零的最小钱数。若newAmount是合理的值，我们也会计算它的找零结果。

最后判断newAmount是否有效，newMin（最少硬币数）是否是最优解和合理值。若都成立意味着有一个比之前更优的答案。最后返回最终结果。

测试算法：console.log(minCoinChange([1,5,10,25],36)); cache会存储1到36的所有结果。以上代码结果是[1,10,25]。