各式各样的演算法 - Greedy、Dynamic Programming 与 Divide and Conquer

题组回顾与观念统整

这一段我们着重在「动态规划」优化，如何从穷举或递回的方法中进一步地将结果记录下来而不用重复计算。例如昨天的「爬第 n 阶楼梯的方法数」与今天的「移动到 m, n 格子的路径数」，都是可以同时使用到「递回」与「动态规划」两种解法。我们也挑选了三题有趣的问题一起体验了这个过程，逐步从「穷举」→「递回」→「动态规划」的练习与尝试优化。

• LLeetCode 双刀流：53. Maximum Subarray
• LeetCode 双刀流：70. Climbing Stairs
• LeetCode 双刀流：62. Unique Paths

➤ 53. Maximum Subarray

方法 ① 直觉先用穷举法（两层回圈）计算符合题目要求的所有可能值将最大的那一组留下来，不过实际上跑测资时不意外的出现 Time Limit Exceeded 的错误。方法 ② 从观察穷举法开始，找出计算过程中可以优化的空间与解法，只要将每次都从头开始改成每回合累加前一回合的结果，这种方法称为贪婪法（Greedy）。第三种方法更一步将累加的过程直接暂存到另一个变数中，把所有可能的结果用「空间」换取「时间」，其实就是动态规划（Dynamic Programming）的基本思路。

➤ 70. Climbing Stairs

延续着动态规划的想法，我们下一题选得「爬楼梯」这道是经典的动态规划题。从这个题目的规则中很直觉的会想到用地递回的方式解题，有一个很明确的迭代过程跟规则。只是递回在这里会遇到时间跟效能上的议题，所以用「空间」换取「时间」来处理，将原本的递回解法转换成动态规划的方式来解。这里大概会有一个小小的笔记，就是关於「暂存」的问大概可以联想到「资料结构」或「递回」的方法来优化，而「递回」又可以与「动态规划」相互转换。

➤ 62. Unique Paths

第三天用 Unique Paths 题目作为是动态规划的小结，这两天的题目都在尝试动态规划的问题，逐步从「穷举」→「递回」→「动态规划」的练习与优化过程，其实会发现「动态规划」跟「递回」根本只有一线之隔，搞懂了递回、动态规划就是把用「空间」换取「时间」的转换。

贪婪法

什麽是贪婪法（Greedy）？

贪婪演算法（Greedy algorithm）是指在求解问题时，在每一个步骤中选择「当下最好的结果/解法」，而不一定会考虑到该解法对最终解的影响。换句话说，贪婪法能考虑到的是区域最佳解（Local Optimization），不代表会同时满足全域最佳解（Global Optimization）。

▇ 常见的贪婪演算法

• Dijkstra's Algrithm： 单一路径之最短距離
• Huffman's Algorithm： 霍夫曼编码或压缩算法

动态规划与分治法

什麽是动态规划（Dynamic Programming）？

动态规划（Dynamic Programming）会将一个大的问题转换成由较小的问题组合而成，透过先处理较小问题并将结果暂存起来，透过小问题的暂存结果再进一步建构出原始问题的可行解。

▇ 常见的动态规划法

• Floyd-Warshall's Algrithm： 所有路径间之最短距離
• Traveling Salesman Problem： 旅行推销员问题
• 0/1 Knapsack Problem： 0/1 背包客问题

分治法（Divide-and-Conquer）？

动态规划其实是分治法（Divide-and-Conquer）的一种延伸与特例，分治法采用由上而下（top-down）的解题思路 方式，可将原始问题分成多个小的，而所有小问题的结果汇整合并（bottom-up）由下而上，之後就可以成为原始问题的最终解法。根据相同的逻辑，动态规划跟递回其实都可以算是分治法的一种实现。

▇ 常见的分治法

• Tower of Hanoi (河内塔)
• Binary tree traversal (二元树追踪)
• Quick sort / Merge sort / Binary Search

从分治法到动态规划

虽然我们说动态规划是一种分治法的延伸，不过如果硬要比较的话可以这样理解。适合动态规划法的题目，通常从原始问题中定义出的问题不是相互独立的，所以我们需要利用现有或新建立变数来暂存所有小问题的结果（不管会不会被用到，都需要将结果记录下来）。

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。