# 第 3 节「动态规划」的算法设计思想

# 空间换时间

由于求解的过程会遇到大量重复的子问题，我们需要记录下来，这是「空间换时间」的思想。

由于需要解决一个问题的所有子问题，这是「穷举」的思想。大家可以百度或者谷歌一下，穷举法看起来「笨笨的」，但是它确实很有用。

「维基百科」上说：数字计算机的普及大大提升了穷举法的易用性。我是这么理解的，人类不擅长的就是干简单重复的事情，但是计算机擅长呀。我们利用了计算机高效、准确的计算能力，帮助我们完成了很多计算任务。

所以，其实「动态规划」没有为一个问题设计专门的解决方案，它就是一个个傻傻地求解所有可能遇到的情况，有些特定问题下会遇到剪枝，大家在做题的过程中可以留意一下。

那么，什么算法是为一个问题设计了专门的解决方案呢？答案是：贪心算法呀！贪心算法充分挖掘了一个问题的特点，使得求解问题的过程只需要 做出在当前看来是最好的选择，而不用考虑其它子问题，并且每个子问题只会遇到一次，求解问题的过程需要记录的变量与问题的规模无关。

因此我们会在一些学习材料中看到：贪心算法没有套路，一题一个样儿。

作者：liweiwei1419 链接：https://suanfa8.com/dynamic-programming/design-thinking 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。