在蓝桥杯的备考过程中，动态规划（Dynamic Programming, DP）是一个非常重要的部分。动态规划题目通常涉及复杂的优化问题，而优化动态规划问题的方法有很多，其中单调队列和斜率优化是两种常用且高效的技巧。本文将通过演示滑动窗口最小值问题，解析凸包技巧在 DP 中的应用场景，帮助大家更好地理解和掌握这些优化方法。
一、动态规划基础回顾
动态规划是一种通过将复杂问题分解为相对简单的子问题的方式来求解复杂问题的方法。其核心思想是将问题分解为重叠子问题，并存储子问题的解以避免重复计算。
二、单调队列优化
单调队列是一种特殊的队列，其内部元素保持单调递增或递减的顺序。单调队列常用于优化一些需要频繁查询区间最值的问题，例如滑动窗口最小值问题。
滑动窗口最小值问题
滑动窗口最小值问题是指在一个数组中，找到每个长度为 $k$ 的窗口中的最小值。使用单调队列可以在 $O(n)$ 的时间复杂度内解决该问题。
算法步骤：
1. 初始化一个单调递增队列。
2. 遍历数组，对于每个元素：
- 如果队列不为空且队首元素已经不在当前窗口范围内，则移除队首元素。
- 移除队列中所有大于当前元素的元素，以保持队列的单调性。
- 将当前元素加入队列。
- 如果当前位置大于等于 $k-1$，则队首元素即为当前窗口的最小值。
代码示例：
from collections import deque
def sliding_window_min(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
if dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] > nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
三、斜率优化
斜率优化是一种用于优化线性动态规划问题的技巧。其核心思想是通过维护一个凸包来减少状态转移的时间复杂度。
凸包技巧在 DP 中的应用
凸包技巧常用于解决一些涉及线性方程的状态转移问题。通过维护一个凸包，可以在 $O(1)$ 的时间复杂度内完成状态转移。
算法步骤：
1. 初始化一个凸包。
2. 对于每个状态，通过凸包快速找到最优的前一个状态。
3. 更新当前状态，并将当前状态加入凸包。
代码示例：
def slope_optimization(nums):
n = len(nums)
dp = [0] * n
queue = []
for i in range(n):
while len(queue) > 1 and slope(queue[-2], queue[-1]) < slope(queue[-1], i):
queue.pop()
queue.append(i)
while len(queue) > 1 and slope(queue[0], queue[1]) < nums[i]:
queue.pop(0)
dp[i] = dp[queue[0]] + nums[i]
return dp
def slope(a, b):
return (dp[b] - dp[a]) / (b - a)
四、总结
动态规划的优化方法多种多样，其中单调队列和斜率优化是两种常用且高效的技巧。通过掌握这些技巧，可以在蓝桥杯等竞赛中更高效地解决动态规划问题。希望本文通过演示滑动窗口最小值问题和解析凸包技巧在 DP 中的应用场景，能够帮助大家更好地理解和掌握这些优化方法。
在备考过程中，建议大家多做练习题，熟悉各种优化技巧的应用场景，并通过实际题目进行巩固。只有不断练习，才能在竞赛中游刃有余，取得好成绩。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
