目录
动态规划
访问量:1756

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化 方法,只不过在计算机问题上应用比较多,比如说让你求最⻓递增子序列 呀,最小编辑距离呀等等。

既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因 为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。

动态规划就这么简单,就是穷举就完事了?我看到的动态规划问题都很难
啊!

首先,动态规划的穷举有点特别,因为这类问题存在「重叠子问题」,如果 暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优 化穷举过程,避免不必要的计算。

而且,动态规划问题一定会具备「最优子结构」,才能通过子问题的最值得 到原问题的最值 


另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化, 穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方 程」才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。 具体什么意思等会会举例详解,但是在实际的算法问题中,写出状态转移方 程是最困难的,这也就是为什么很多朋友觉得动态规划问题困难的原因,我 来提供我研究出来的一个思维框架,辅助你思考状态转移方程:

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者
主要是让你明白什么是重叠子问题(斐波那契数列严格来说不是动态规划问
题),后者主要举集中于如何列出状态转移方程。

请读者不要嫌弃这个例子简单,只有简单的例子才能让你把精力充分集中在 算法背后的通用思想和技巧上,而不会被那些隐晦的细节问题搞的莫名其 妙。想要困难的例子,历史文章里有的是