什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

可以这样理解，算法是用来解决特定问题的一系列步骤；算法必须具备如下3个重要特性：

有穷性。执行有限步骤后，算法必须中止。
确切性。算法的每个步骤都必须确切定义。
可行性。特定算法须可以在特定的时间内解决特定问题。

分治法

分而治之是算法设计中的一种方法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

关于分而治之的实现，都会经历三个步骤：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题
解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题
合并：将各子问题的解合并为原问题的解

实际上，关于分而治之的思想，归并排序同样经历了实现分而治之的三个步骤：

分解：把数组从中间一分为二
解决：递归地对两个子数组进行归并排序
合并：将两个字数组合并称有序数组

同样关于快速排序的实现，亦如此：

分：选基准，按基准把数组分成两个字数组
解：递归地对两个字数组进行快速排序
合：对两个字数组进行合并

同样二分搜索也能使用分而治之的思想去实现，代码如下：

function binarySearch(arr,l,r,target){
  if(l> r){
    return -1;
  }
  let mid = l + Math.floor((r-l)/2)
  if(arr[mid] === target){
    return mid;
  }else if(arr[mid] < target ){
    return binarySearch(arr,mid + 1,r,target)
  }else{
    return binarySearch(arr,l,mid - 1,target)
  }
}

动态规划

动态规划，同样是算法设计中的一种方法，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

常常适用于有重叠子问题和最优子结构性质的问题。

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决；然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

一般这些子问题很相似，可以通过函数关系式递推出来，例如斐波那契数列，我们可以得到公式：当 n 大于 2的时候，F(n) = F(n-1) + F(n-2) ，f(10)= f(9)+f(8),f(9) = f(8) + f(7)…是重叠子问题，当n = 1、2的时候，对应的值为2，这时候就通过可以使用一个数组记录每一步计算的结果，以此类推，减少不必要的重复计算。

适用场景

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

关于动态规划题目解决的步骤，一般如下：

描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解

与分治法区别

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，而分而治之的子问题是相互独立的；若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

综上，可得：

动态规划：有最优子结构和重叠子问题
分而治之：各子问题独立

贪心算法

贪心算法，又称贪婪算法，是算法设计中的一种思想。

其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的。

举个零钱兑换的例子，如果你有1元、2元、5元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最少；如果现在你要兑换11元，按照贪心算法的思想，先选择面额最大的5元钱币进行兑换，那么就得到11 = 5 + 5 + 1 的选择，这种情况是最优的；但是如果你手上钱币的面额为1、3、4，想要兑换6元，按照贪心算法的思路，我们会 6 = 4 + 1 + 1这样选择，这种情况结果就不是最优的选择。

从上面例子可以看到，贪心算法存在一些弊端，使用到贪心算法的场景，都会存在一个特性：

一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。

至于是否选择贪心算法，主要看是否有如下两大特性：

贪心选择：当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择
最优子结构：如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在

回溯算法

回溯算法，也是算法设计中的一种思想，是一种渐进式寻找并构建问题解决方式的策略。

回溯算法会先从一个可能的工作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

使用回溯算法的问题，有如下特性：

有很多路，例如一个矩阵的方向或者树的路径
在这些的路里面，有死路也有生路，思路即不符合题目要求的路，生路则符合
通常使用递归来模拟所有的路

例如经典使用回溯算法为解决全排列的问题，如下：

一个不含重复数字的数组 nums ，我们要返回其所有可能的全排列，解决这个问题的思路是：

用递归模拟所有的情况
遇到包含重复元素的情况则回溯
收集到所有到达递归终点的情况，并返回

用代码表示则如下：

var permute = function(nums) {
  const res = [], path = [];
  backtracking(nums, nums.length, []);
  return res;

  function backtracking(n, k, used) {
    if(path.length === k) {
      res.push(Array.from(path));
      return;
    }
    for (let i = 0; i < k; i++ ) {
      if(used[i]) continue;
      path.push(n[i]);
      used[i] = true; // 同支
      backtracking(n, k, used);
      path.pop();
      used[i] = false;
    }
  }
};

总结

分而治之、动态规划、贪心策略三者对应的经典问题如下：

分治法

归并排序
最大子数组问题1
逆序计数问题
快速排序
次序选择问题

动态规划

0-1背包问题
最大子数组问题2
最长公共子序列问题
最长公共子串问题
最小编辑距离问题
钢条切割问题
矩阵链乘法问题

贪心算法

部分背包问题
霍夫曼编码
活动选择问题