动态规划是求解最优化问题的一种方法；动态规划虽然空间复杂度一般较大，但时间效率可观。但是，动态规划在求解中也会存在一些不必要、或者重复求解的子问题，这时就需要进行进一步优化。
在NOI及省选赛场上，一般的裸动态规划可能难以达到所要求的时间效率。本文收录了在时间效率上动态规划的三大优化：四边形不等式，斜率优化，单调队列优化。另外，也收录了解决NP问题小规模求解中，优于搜索的状态压缩动态规划。
关键词：动态规划优化，四边形不等式，斜率优化，单调队列，状态压缩动态规划。
2021-04-20 15:06:33
771KB
1
最大子段和问题，可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n，及n个整数。程序应该给出良好的用户界面，输出最大子段相关信息，包括：最大字段和、起始下标、终止下标等。
扩展：可以求解数组中任意区间段内的最大子段和及该子段和的起始下标和终止下标。
2021-04-14 22:00:48
940B
1