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

  |  

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

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


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

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

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

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

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

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

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

求最小化的指标 $S$。

1
2
3
4
5
6
7
8
9
10
11
12

输入格式
第一行包含一个整数 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$ 的第二维是稀疏的,其取值范围就是 A 的取值范围。将该范围离散化到 $0,\cdots,m-1$,然后用 $0$ 到 $m-1$ 之间的整数代表 $A$ 的取值范围中的值,并且 $0$ 到 $m-1$ 的大小关系代表了对应在 $A$ 中的值的大小关系。

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

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

状态转移方程中的 $\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$ 阶段的各状态的过程如下:

1
2
3
4
5
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)

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
26
27
28
29
30
31
32
33
34
35
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()

Share