通过离散化处理状态表示中的稀疏维度

摘要: 状态表示中的附加信息要素非常稀疏时，可以用离散化的方式来处理

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

---

对于动态规划问题，有时仅仅把阶段要素放到 DP 状态中，不足以执行转移。也就是说在 DP 状态中要附加某种信息，才能找到某种最优子结构来执行转移。

在文章 阶段不足以表示可推导的状态：附加信息作为状态维度 中我们详细分析过这种情况的处理方法。

附加信息可能是稀疏的，在那篇文章中我们是用哈希表来处理的。也就是在每个阶段上塞一个哈希表进去，表示该阶段下的附加信息所有可能取值。本文我们通过离散化来处理状态表示中稀疏的附加信息维度。

另外本题还涉及到了排除无效决策优化DP：通过数学性质把附加信息的取值范围缩小，减少无效状态。

构造非严格递增序列，最小化某个指标

• 273. 分级

给长度为 N 的序列 A，构造一个长度为 N 的序列 B，满足：

1. B 是非严格递增或非严格递减的
2. 最小化 $S = \sum\limits_{i=1}\limits^{N}|A_{i} - B_{i}|$

求最小化的指标 $S$。

输入格式
第一行包含一个整数 N。

接下来 N 行，每行包含一个整数 Ai。

输出格式
输出一个整数，表示最小 S 值。

数据范围
1<=N<=2000,
0<=Ai<=1e6

输入样例：
7
1
3
2
4
5
3
9
输出样例：
3

算法：动态规划

阶段划分

考虑前 i 个数的构造时，$\sum\limits_{j=1}\limits^{i}|A_{i} - B_{i}|$ 的最小值。这样考虑的话，阶段是已经处理完的前缀的长度。

因为有单调性的要求，在转移的时候，为了确定 $B_{i}$ 定什么值，还需要知道 $B_{i-1}$ 的值才可以。

附加信息

也就是说，仅把 DP 的阶段要素放在 DP 状态中不足以进行转移，因此最直接的方法就是把状态表示增加一维，作为附加信息。

状态表示

定义 $dp[i][k]$ 表示完成前 $B[0..i]$ 的构造，其中 $B[i] = k$ 时，$S$ 的最小值。

剪枝优化DP：基于数学性质

在阶段 $i$ 考虑 $B[i]$ 的构造时，取值范围很大。但由状态表示，$B[i]$ 的每个取值都对应阶段 $i$ 下的一个状态。不可能把所有可能取值都推一遍。

通过观察可以发现一种性质：使得指标最小化若干种 $B[i]$ 的取值中，必有一种是在 $A$ 中出现过的。这样在考虑 $B[i]$ 的构造时，仅需把 $A$ 的取值范围的所有值推导一遍即可，取到的指标最小最就是 $B[i]$ 取所有可能值所得的指标最小值。

相当于通过发现好的性质，这种性质保证了剪枝后留下的部分中一定存在最优解。使得我们可以通过在减小后的搜索空间中（$B[i]$ 取 A 中出现过的值所得的指标最小值）得到全局最优解（$B[i]$ 取所有可能值所得的指标最小值）。这样在阶段 $i$ 下的附加信息取值范围（搜索空间）大大减少，去掉了很多无效状态。

引理

在满足 $S$ 最小化的前提下，存在构造 B 的方案，使得 B 中的数值都在 A 中出现过。

证明（数学归纳法）

命题对 $N=1$ 成立。

假设引理对 $N=k-1$ 成立，此时构造的序列为 $B_{1}, B_{2}, \cdots, B_{k-1}$。

考虑 $N=k$ 时，$B_{k}$ 的取值。若 $B_{k-1} \leq A_{k}$ 则令 $B_{k} = A_{k}$，命题成立；若 $B_{k-1} > A_{k}$ 则比较复杂，下面证明存在 $j$，使得 $B_{j}, B_{j+1}, \cdots, B_{k}$ 为同一个值 $v$。

设 $A_{j}, A_{j+1}, \cdots, A_{k}$ 的中位数为 $mid$，根据 货仓选址与安排邮筒，若 $mid \geq B_{j-1}$，则 $v=mid$；若 $mid < B_{j-1}$ 则 $v=B_{j-1}$，这两种情况 $B_{1}, \cdots, B_{k}$ 中的数均在 A 出现过。

$\Box$

有了以上引理，在考虑 B 中的每个值时，候选范围仅在 A 的取值范围中选即可。

状态转移方程

以单调递增地构造 $B[i]$ 为例，假设 $B_{i}$ 的选择为 $k$，由引理，$B_{i-1}$ 的选择仅考虑 $A$ 的取值范围中小于等于 $k$ 的那些即可。

$$dp[i][k] = \min\limits_{\substack{j \leq k \\ j \in A}}(dp[i - 1][j] + |A[i] - k|)$$

稀疏维度处理：离散化

$dp$ 的第二维是稀疏的，其取值范围就是 A 的取值范围。将该范围离散化到 $0,\cdots,m-1$，然后用 $0$ 到 $m-1$ 之间的整数代表 $A$ 的取值范围中的值，并且 $0$ 到 $m-1$ 的大小关系代表了对应在 $A$ 中的值的大小关系。

设 $A$ 排序去重后的结果为 $a$，则 $dp[i][k]$ 表示 $B_{i}$ 取值为 $a[k]$，这样状态转移方程改为：

$$dp[i][k] = |A[i] - a[k]| + \min\limits_{\substack{0 \leq j \leq k}}dp[i - 1][j]$$

决策单调性：决策集合递增而目标函数不变

状态转移方程中的 $\min$ 部分，如果每次都是枚举 $j=0,\cdots,k$，则状态转移一次的时间复杂度就成了 $O(N)$。

仔细观察可以发现这是一个决策候选集合仅增加不减少的情况，把满足 $0 \leq j \leq k$ 的 $j$ 构成的集合称为状态 $dp[i][k]$ 转移时的决策集合，记为 $S(i, k)$。

其中 $i$ 代表阶段，当阶段 $i$ 固定，$k \rightarrow k + 1$ 时，$j$ 的取值范围从 $[0, k]$ 到 $[0, k+1]$，也就是 $S(i, k)$ 与 $S(i, k + 1)$ 的区别仅在于 $k+1$ 加入了决策候选集。

因此阶段 $i$ 刚开始推导时，初始化一个变量 $mx$，当附加信息按照 $k=0,1,\cdots,m-1$ 从小到大推导时，$mx$ 始终记录 dp[i][0..k] 的最小值，这样在推导 $k+1$ 时，仅需考虑新增加的候选决策 $dp[i - 1][k + 1]$ 即可。

于是推导第 $i$ 阶段的各状态的过程如下：

dp[i][0] = |A[i] - a[0]|
mx = dp[i - 1][0]
for k = 1,2,...,m-1:
    dp[i][k] = |A[i] - a[k]| + mx
    mx = min(mx, dp[i - 1][k])

代码 (Python)

def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    # 离散化
    a = sorted(set(A))
    m = len(a)

    def solve(A):
        # 构造非严格单调递增的 B
        dp = [[0 for _ in range(m)] for _ in range(N)]
        for k in range(m):
            dp[0][k] = abs(A[0] - a[k])

        for i in range(1, N):
            mx = dp[i - 1][0]
            dp[i][0] = abs(A[i] - a[0]) + mx
            for k in range(1, m):
                mx = min(mx, dp[i - 1][k])
                dp[i][k] = abs(A[i] - a[k]) + mx

        return min(dp[N - 1])

    # B 非严格单调递增的情况
    ans1 = solve(A)
    # B 非严格单调递减的情况
    ans2 = solve(list(reversed(A)))

    print(min(ans1, ans2))


if __name__ == "__main__":
    main()

---