动态规划中如何融入优化策略以提升算法效率？

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

【以下内容仅为个人在学习中的感悟与想法，本人水平有限，如有错误及不足之处，还请各位大师指正，谢谢！】

+ 引言 +

在动态规划领域，PaperHammer 是一个值得关注的研究方向。本文将探讨动态规划在 PaperHammer 中的应用，并分析其优缺点。

引言

前一篇文章（有关动态规划 - PaperHammer - 自由互联 (cnblogs.com)）我们探讨了动态规划及其分析方法，但在做题或面试时往往会需要我们对空间或时间进行优化，尤其是对空间的优化尤为常见。动态规划本就难度较大，对于尚处学习阶段的同学，能写出来就算很不错了。在此，本人将分享我在做题时的想法与见解，并和大家一起学习新的知识，如有错误或更好的思想还请各位大佬留言指正，谢谢！

复杂度分析

复杂度分为时间复杂度与空间复杂度，其不代表程序正真运行时间与所占空间，只反映在执行时间或占用空间随数据规模增大的变化趋势，以最高阶的变化趋势来分别代表整个程序的时空复杂度。

（一）空间

空间复杂度取决于我们用来记录之前数据的存储结构。一般地，在DP中常见的空间复杂度有O(N)与O(N²)或者更大，但一般不超过O(N³)，通常我们需要对其指数至少减小1或降阶，以达到相应的需求。减少的关键思想在于，判断我们所存储过的数据是否会被再次访问，是否可以不用一直存储。通常采用画表的方式进行判断。