【Day35】[演算法]-常见的演算法策略Algorithmic Patterns

分治法（Divide and conquer）

又称分而治之法，是最常被使用的策略方式，原理是将一个难以直接解决的大问题，依据相同的概念分割成多个子问题，再各个击破，分而治之，不断地将子问题缩小，最後再将各子问题的解答合并起来。

之前介绍多种的演算法，就是运用这样的策略。
合并排序
快速排序
基数排序
二分搜寻

动态规划法（Dynamic Programming）

动态规划法类似上述的分治法，依样是将大问题分割成多个子问题来解决，只是有些子问题可能是重复的，所以会发生重复计算的问题，动态规划与分治法最大不同在於会将重复计算的子问题将其记忆化储存，来解决重复计算的问题，用空间换取时间的概念来加速执行效能。

之前介绍改良版费波那契数列就是运用这样的策略。

贪婪法 (Greed Algorithm)

又称贪心法，原理是在每一次解决步骤时都以贪心为原则，采取当下最有利的选择，当步骤都结束後进而希望是最有利的解答。

假设今天你今天用一张100元钞票买了18元饮料，你希望全部找的零钱硬币数量要是最少，该如何找钱?

一开始先选择50元 x1
接着10元 x3
再来5元 x0
最後1元 x2

总共6枚硬币，最佳解答。

回溯法（Backtracking）

原理是先列出此阶段的所有分支可能性，接着排除掉不可能为解答的分支，再来往其中一个分支执行，若此阶段已经确定所有分支都不为解答时，则退回上一阶段，往其他分支执行，来避免多余无效的步骤。

深度优先搜寻，就是运用这样的策略。

分支界定法（Branch and bound）

有点类似地毯式搜索，列出此阶段的所有分支可能性，开始执行此阶段所有分支，若此阶段都不为解答时，其中一个分支成为新阶段，重复上述步骤执行。

广度优先搜寻，就是运用这样的策略。