在信息学奥赛CSP-J的备考过程中，到了第5个月的冲刺阶段，算法强化是非常关键的一部分，尤其是动态规划的优化技巧。
一、动态规划基础回顾
动态规划是一种解决多阶段决策过程最优化问题的方法。它通常用于解决具有重叠子问题和最优子结构性质的问题。例如，在计算斐波那契数列时，传统的递归方法会有大量的重复计算，而动态规划可以通过记录已经计算过的结果来避免这种重复，提高效率。
二、滚动数组（压缩状态空间）
- 知识点内容
- 滚动数组是动态规划中一种常用的空间优化技巧。当动态规划的状态转移方程只依赖于前几个状态时，我们可以使用滚动数组来减少存储状态的空间。例如，在一个一维的动态规划问题中，如果我们只需要当前状态和前一个状态来计算下一个状态，那么我们就不需要存储所有的中间状态，而只需要两个变量（或者一个数组的两个元素）来交替存储当前状态和前一个状态即可。
- 对于二维动态规划问题，如果状态转移方程只依赖于同一行的相邻元素或者相邻行的特定元素，我们也可以通过合理地设计滚动数组来减少空间的使用。
- 学习方法
- 理解状态转移的本质。要明确每个状态是如何从前面的状态得到的，这样才能够确定哪些状态是可以舍弃的。
- 多做练习题。通过实际的题目来感受滚动数组的应用场景。比如在一些数字三角形问题或者最长公共子序列问题的变形中，尝试使用滚动数组来优化空间复杂度。
三、单调队列优化
- 知识点内容
- 单调队列是一种特殊的队列，它可以在O(1)的时间复杂度内获取队列中的最大值或者最小值。在动态规划中，当状态转移方程涉及到在一定范围内取最优值时，单调队列就可以发挥作用。例如，在一个数组中，要找到每个位置i之前的k个元素中的最小值，并且这个最小值与当前元素的某种运算结果是最优的，就可以使用单调队列来维护这个最小值。
- 单调队列的维护原则是保持队列中的元素单调递增或者单调递减。当新元素进入队列时，如果它破坏了队列的单调性，就从队尾开始删除元素，直到满足单调性为止；当需要获取队首元素时，如果队首元素已经超出了我们所需要的范围，就将其从队首删除。
- 学习方法
- 手动模拟单调队列的操作过程。可以拿一个简单的数组，按照单调队列的规则进行入队、出队操作，加深对单调队列的理解。
- 结合动态规划问题进行分析。在做动态规划的题目时，思考哪些地方可以使用单调队列来优化，然后对比使用单调队列前后的时间复杂度和空间复杂度。
四、例题演示
以一个经典的区间覆盖问题为例。假设有n个区间[Ai,Bi]，要选择最少的区间覆盖[1,m]这个区间。
如果不使用优化技巧，我们可以使用二维动态规划，设dp[i][j]表示覆盖到位置j且最后一个区间是第i个区间的最小区间数。但是这样会导致空间复杂度过高。
如果我们使用滚动数组，因为我们只需要知道当前位置和前一个位置的dp值就可以进行状态转移，所以可以将二维数组压缩成一维。
再进一步，如果我们发现状态转移只与一定范围内的dp值有关，并且这个范围内的最小值是我们所需要的，那么我们就可以使用单调队列来优化这个过程。
总之，在CSP - J的备考冲刺阶段，掌握动态规划的这些优化技巧，如滚动数组和单调队列优化，能够有效地降低空间复杂度，提高算法的效率，从而在竞赛中取得更好的成绩。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
