动态规划在解决哪些复杂问题上具有显著优势？

本文共计4474个文字，预计阅读时间需要18分钟。

【以下内容仅为个人在学习过程中的感想与想法，本人水平有限，目前处于学习阶段的初级阶段，如有错误及不足之处，还请各位大佬指正，感谢解答！】

#Updated

引言

通过目前参与的各类比赛和网友的面经，不难发现动态规划一直是各类竞赛和面试中的高频和难点，但其最优化的思想在生产生活中的各大领域都具有许多作用。撰写这篇随笔的目的既是为了自我学习的总结，也是为了能得到更多的帮助与见解，从而提高自己。在此，我将以自己的想法叙述我解决动规的过程。

动规简述

动态规划本质是记忆化搜索，即记录之前行为所产生的结果，这也是其比纯搜索算法更快的原因。

举个例子：计算斐波那契数列（f[n] = f[n – 1] + f[n – 2]），当我们要计算f[8]时，会使用之前已经算过的f[6]与f[7]直接相加得到答案，而不是再从f[0]开始从头计算一遍每个值，这样当数据量很庞大时就可以节省很多时间。

动规特征

　　1. 重叠子问题：每一步，在操作上都具有明显的相同相似性。

　　2. 最优子结构：最终问题的最优解基于每一步的最优解而得出。