跳跃型DP入门

跳跃型 DP (线性 DP 进阶)

算法简介

• 核心特征：$dp[i] = \max/ \min \{ dp[j] \} + \text{cost}$，其中$j i$且满足特定限制（如数值大小、距离范围、属性匹配等）。
• 时间复杂度：朴素做法为$O(N^2)$，通过优化查找可降至$O(N \log N)$或$O(N)$。
• 基本枚举顺序：通常为线性枚举$i$，但在计算$dp[i]$时需要高效查找$j$。

------



一、朴素限制模型 ($O(N^2)$)





1. 核心原理



这是跳跃型 DP 的基础。题目规定了明确的转移条件（如 LIS 中的$a[j] a[i]$），但数据范围允许$O(N^2)$。侧重于理解状态定义和合法性判断。

• 状态转移：

$$dp[i] = \max_{\substack{0 \le j i \\ \text{check}(j, i) \text{ is true}}} \{ dp[j] \} + 1$$

• 经典场景：
- 最长上升子序列 (LIS)
- 合唱队形 (双向 LIS)
- 满足特定公差/条件的子序列



2. 常用技巧



• DP 状态定义
当正向依赖关系复杂时，尝试定义$dp[i]$为“从$i$开始到结尾”的最优解（如《尼克的任务》）。

• 多维状态
当简单的$dp[i]$无法区分不同情况时，增加维度。例如$dp[i][\text{diff}]$表示以$i$结尾且公差为$\text{diff}$的链长。



3. 代码模板





// 朴素 LIS 模板
for (int i = 1; i <= n; i++) {
    dp[i] = 1; // 初始化：自身构成长度为 1 的序列
    for (int j = 1; j < i; j++) {
        // 核心：检查跳跃条件
        if (a[j] < a[i]) { 
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    ans = max(ans, dp[i]);
}




二、特殊查找与性质优化模型





1. 核心原理



当$N$达到 $10^5$ 时，不能遍历 $j$。我们需要利用题目性质（如数值单调性、二进制位、因数等），将查找前驱的复杂度从$O(N)$降为$O(\log N)$或$O(1)$。

• 核心思想：不要遍历“位置”，而是遍历“值”或“属性”。我们只关心具有某种属性的$j$中，$dp[j]$最大的那个。



2. 常用技巧



• 贪心 + 二分 (LIS 进阶)
维护一个辅助数组q，其中q[len]存储长度为len的子序列中结尾最小的数值。利用std::lower_bound快速查找。

• 位运算桶 (Bitmask)
若限制条件是 $a[j] \& a[i] \ne 0$，则开一个数组max_val[30]，记录第$k$位为 1 的最大 dp 值。

• Vector 挂链
若 $j$ 是离散的区间右端点，可以用vector<int> end_at[i]预处理所有以$i$结尾的区间，DP 时直接遍历 vector。



三、单调队列优化模型





1. 核心原理



这类问题通常要求“跳跃距离”在一定范围内，即$L \le i - j \le R$。这构成了典型的滑动窗口最值问题。

• 状态转移：

$$dp[i] = \max_{i-R \le j \le i-L} \{ dp[j] \} + \text{cost}[i]$$

• 数据结构：使用双端队列 (std::deque) 维护候选集合。队列中存储下标，且对应的$dp$值是单调递减的。



2. 常用技巧



• 队首出队 (过期)
当q.front() < i - R时，说明队首元素已经超出了最大跳跃距离，必须扔掉。

• 队尾清理 (劣汰)
当新决策$dp[i-L]$优于队尾元素的决策时，队尾元素永远不会成为最优解，直接弹出。

• 二分答案 + 单调队列
常见于求“最小代价”或“最大距离”的问题（如《跳房子》），外层二分答案，内层用单调队列 DP 进行check。

• 权值数据结构 (BIT / 线段树)

3. 代码模板

// 单调队列优化 DP 模板
deque<int> q;
for (int i = 1; i <= n; i++) {
    // 1. 尝试将 i-L 加入候选队列 (注意边界)
    int pre = i - L;
    if (pre >= 0) {
        // 维护单调性：如果新来的比队尾优，队尾就没用了
        while (!q.empty() && dp[q.back()] <= dp[pre]) q.pop_back();
        q.push_back(pre);
    }
    
    // 2. 移除过期的候选 (距离超过 R)
    while (!q.empty() && q.front() < i - R) q.pop_front();
    
    // 3. 取队首作为最优决策进行转移
    if (!q.empty()) {
        dp[i] = dp[q.front()] + cost[i];
    }
}