算法动态规划

单调队列优化DP

字数统计: 236字   |   阅读时长: 1分
, , ,

摘要: 单调队列优化 DP 的思路以及一些例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

使用数据结构优化动态规划的状态转移过程是很常见的思路，例如 平衡树优化DP、哈希表优化DP。单调队列也是一种，本文我们首先看一下单调队列优化 DP 适合解决什么样的状态转移方程。然后通过解决 1425. 带限制的子序列和，来看一下单调队列优化 DP 的具体思路和做法。

单调队列优化DP

当状态转移方程有以下形式的时候，可以考虑单调队列优化 DP。

其中 $f(i, j)$ 可以分为仅与 $i$ 相关和仅与 $j$ 相关的两部分: $f(i, j) = g1(i) + g2(j)$。这样转移方程可以写为：

于是在求 $dp[i]$ 时，要问：$i$ 左侧的区间范围 $L(i)<=j<=R[i]$ 的窗口中，$dp[j] + g2(j)$ 的最大值是多少。

这一问是滑动窗口最值问题，可以用单调队列解决，类似的问题可以参考文章：单调队列。

题目：1425. 带限制的子序列和

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

提示：

1
2
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

示例 1：
输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：
输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：
输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

算法：单调队列优化 DP

基础动态规划

1
2
3
4
5
6
7
8
状态定义：
dp[i] := [0..i] 且以 i 为终点的最大子序列和

案答：
max(dp[i]) 

初始化：
dp[0] = nums[0]

转移方程：

单调队列优化

在求 dp[i] 时需要回答提问： i 左侧长度最大为 K - 1 的窗口中，dp 的最大值是多少。

在推进 i 时，用 deq 维护系列对应的 dp 值单调递减的下标队列，在求 dp[i] 时，deq 中维护的是 dp[max(0, i - K + 1) .. i - 1] 的长为 K - 1 单调递减队列。

此时 mx = dp[deq.front()] 为当前滑窗的最大值。用这个最大值更新答案。ans = (ans, max(0, mx))。

在求完 dp[i] 准备从队尾将 i 压进 deq 之前，需要删两部分内容。

  • 一部分是队尾的 dp 值小于等于待压进的 dp[i] 的：
1
2
while(!deq.empty() && dp[deq.back()] <= dp[i])
    deq.pop_back();
  • 另一部分是队头的下标 deq.front() 与 i 的长度 i - deq.front() + 1 如果大于 K - 1 的话，需要弹出：
1
2
if(deq.front() <= i - K + 1)
    deq.pop_front();

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        int K = k + 1; // 窗长 K
        vector<int> dp(n);
        dp[0] = nums[0];
        deque<int> deq;
        deq.push_back(0);
        int ans = dp[0];
        for(int i = 1; i < n; ++i)
        {
            int mx = dp[deq.front()];
            dp[i] = nums[i] + max(0, mx);
            ans = max(ans, dp[i]);
            while(!deq.empty() && dp[deq.back()] <= dp[i])
                deq.pop_back();
            deq.push_back(i);
            // 队列中维护 [i - K + 2, i]  长度为 K - 1
            if(deq.front() <= i - K + 1)
                deq.pop_front();
        }
        return ans;
    }
};
Share