快速过算法设计思想

1. 分而治之

算法设计的一种方法。

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

归并排序

分：把数组从中间一分为二
解：递归地堆两个子数组进行归并排序。
合：合并有序子数组

快速排序

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

2. 动态规划

将一个问题分解为相互重叠的子问题，通过反复求解子问题来解决原来的问题

动态规划和分而治之区别在于，他们的子问题是否是独立，子问题是否会互相干扰。

斐波那契数列

定义子问题 F(n) = F(n-1) + F(n-2)

反复执行：从 2 循环到 n，执行上述公式。

3. 贪心算法简介

期盼通过每个阶段的局部最优解，从而达到全局的最优解，但结果不一定是最优。

贪心法，又称贪心算法，贪婪算法，在对问题求解时，总是做出在当前看来最好的选择，期望通过每个阶段的局部最优选择达到全局最优，但结果不一定最优

适用场景：简单的说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪心算法的到最后的最优解，这种子问题最优解称为最优子结构

贪心算法与动态规划的不同点在于它对每个子问题的解决方案都做出当前的最优选择，不能回退，而动态规划会保留之前的运算结果，并根据之前的结果进行选择，有回退的功能，贪心是动态规划的理想化的情况。

解法： 数组 + 贪心

// 解题思路：

// 贪心：局部最优，见好就收，见差就不懂，不做长远打算
// 新建一个变量用来统计总记录
// 遍历价格数组，如果当前价格比昨天高就在昨天买，今天卖，否则就不交易。
// 返回利润之和
var maxProfit = function(prices) {
    let profit = 0;
    for (let i = 1; i < prices.length; i+=1) {
        if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i-1]
        }
    }
    return profit;
};

4. 回溯算法

渐进式寻找并构建问题解决方式的策略，回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

适用场景：

有很多路，这里有死路也有出路吗，通常需要递归来模拟所有的路。