0%

动态规划是一种牛逼闪闪的算法思想。

先上维基百科的解释:

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。
通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:
一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。
这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
阅读全文 »