决策单调性的简单情况:决策候选集随状态推导递增而目标函数不变

  |  

摘要: 决策单调性的简单情况

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


决策候选集与最优决策

考虑以下状态转移方程:

在推导状态 $dp[i]$ 时,$1 \leq j \leq i$ 均对应一个决策,我们要求的是 $f(j, i)$ 在 $1\leq j < i$ 范围内的极小值。

常规方法是一一枚举,时间复杂度 $O(i)$。如果 $f(j, i)$ 具备某些好的性质,可以使得最优决策具有单调性,即随着 $j$ 的范围 $[1, i]$ 增加,最优决策位置 $opt(i)$ 也单调增加,这种性质称为决策单调性。这样在从小到大推导 $i$ 的时候,$j$ 的最优决策点肯定不小于上一轮 $i - 1$ 时的最优决策,即 $opt(i-1) \leq opt(i)$。

目标函数与 $i$ 无关

如果目标函数 $f(j, i)$ 与 $i$ 无关,那么决策候选集单调增加时目标函数不变,这是决策单调性的简单情况。

在转移的过程中,把满足 $0 \leq j < i$ 的 $j$ 构成的集合称为状态 $dp[i]$ 转移时的决策集合,记为 $S(i)$。

注意这里的特点,$\min$ 的目标函数与 $i$ 无关。

因此当 $i \rightarrow i + 1$ 时,$j$ 的取值范围从 $[0, i)$ 变为 $[0, i+1)$,即 $i$ 有可能进入新的决策集合(需要满足某些条件),即 $S(i)$ 与 $S(i + 1)$ 的区别仅在于 $i$ 是否加入。即:

这是一个在状态 $i$ 推导过程中,$j$ 的决策集合始终只增多不减少的情况。同时目标函数与推导的变量$i$无关,即目标函数不变,因此没当 $i \rightarrow i + 1$ 时,判断是否把可能新加入候选集的决策(在这个问题中是 $i$)加入决策候选集即可。这里决策候选集是单调增加的,目标函数不变,最优决策自然也单调增加,这可以理解为是决策单调性的一种简单情况。

这种情况下,在推导阶段 $i$ 的过程中,用一个变量 $opt$ 维护当前的最优决策,每推导一次 $i$,维护最优决策的变量 $opt$ 就向前推进若干,或者保持不动。具体怎么实现,要基于前面的 $condition$ 是什么。

本文的题目就是这种情况,此外,下面两道题也是类似的处理方法,可以参考:

目标函数与 $i$ 有关

对于 $dp[i] = \min\limits_{1\leq j \leq i}f(j, i)$,如果目标函数 $f(j, i)$ 与 $i$ 有关,那么决策单调性就不好发现了,需要一些灵感才行。四边形不等式是一种满足判定决策单调性的情况。

如果上述转移方程满足决策单调性,即 $opt(i) \leq opt(i+1)$,由于目标函数与 $i$ 有关时,我们只能知道 $1, 2, \cdots, opt(i)-1$ 不会是最优决策,但是 $opt(i), opt(i) + 1, \cdots, i-1$ 中谁是最优决策并不确定。

如果暴力的话,需要对这些 $j=opt(i),opt(i)+1, \cdots, i-1$ 计算当前阶段 $i$ 的新目标函数 $f(i, j)$,这个时间复杂度最坏也是 $O(N)$。一种处理方式是推导完阶段 $i$ 时,做一步判断:在 $1,\cdots,i$ 范围内,$i$ 可以作为后续的 $i+1,\cdots n-1$ 中哪些阶段的最优决策点。具体细节与代码模板参考文章 决策单调性优化DP:四边形不等式


264. 丑数 II

给你一个整数 n ,请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

提示:

1
1 <= n <= 1690

示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。

算法:动态规划

记 $dp[i]$ 表示第 $i$ 个丑数,其中 $i$ 为阶段。初始时 $dp[1] = 1$,答案即为 $dp[n]$。

假设当前正在推导 $dp[i]$,此时 $dp[1], \cdots, dp[i-1]$ 已经推导完成。由于只有 $2, 3, 5$ 这 3 个质因子可选,因此 $dp[i]$ 有 3 种转移的可能:

  • 从 $dp[1], \cdots, dp[i-1]$ 中的某个状态乘以 2 转移过来,记为 $2dp[j_{2}]$,其中 $1 \leq j_{2} \leq i-1$。
  • 从 $dp[1], \cdots, dp[i-1]$ 中的某个状态乘以 3 转移过来,记为 $3dp[j_{3}]$,其中 $1 \leq j_{3} \leq i-1$。
  • 从 $dp[1], \cdots, dp[i-1]$ 中的某个状态乘以 5 转移过来,记为 $5dp[j_{5}]$,其中 $1 \leq j_{5} \leq i-1$。

于是状态转移方程为:

现在问题就在于 $j_{2}, j_{3}, j_{5}$ 分别取多少。比较直接的方法是把 $[0, i-1]$ 范围的状态都遍历一遍,取最小值,但这样的话状态转移的时间复杂度就大了。

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

以 $j_{2}$ 为例,由于 $dp$ 是单调递增的,所以为了让 $2dp[j_{2}]$ 最小,$j_{2}$ 应该尽可能小。另一方面,当 $j_{2}$ 小到某个限度的时候,$2dp[j_{2}]$ 就比 $dp[i-1]$ 还小了,那也不行。

总结来说,对于 $dp[i]$,$j_{2}$ 这一路的最优决策是 $2dp[j_{2}] > dp[i - 1]$ 的最小的 $j_{2}$,记为 $opt_{2}(i)$,由于目标函数与 $i$ 无关,所以随着 $i \rightarrow i+1$ 时,$opt_{2}(i) \leq opt_{2}(i+1)$,即因子 2 这一路满足决策单调性

另一方面,由于目标函数与 $i$ 无关,这样我们就可以在推导阶段 $i$ 时,仅维护一个 $j_{2}$,表示上一阶段因子 $2$ 这一路的最优决策点,在后续阶段中,这个最优决策点 $j_{2}$ 及其目标函数值 $2dp[j_{2}]$ 可以复用。只需要将新增的候选决策与 $2dp[j_{2}]$ 对比即可。

具体过程就是在推导阶段 $i$ 的过程中,用一个变量维护当前的最优决策,每推导一次 $i$,维护最优决策的变量就向前推进若干,或者保持不动

这里还有一个基于问题本身的额外性质,即:当前阶段 $i$ 如果因子 2 这一路作为最优决策,那只有可能是 $j_{2} + 1$。这样在维护因子 2 这一路的最优决策变量时,仅需考虑是否推进到 $j_{2} + 1$ 即可。

类似地,$j_{3} + 1, j_{5} + 1$ 是因子3和因子5这两路的最优决策候选。具体选谁,要看这三个候选之间的对比。

这样在推导 $dp[i]$ 时,直接比较 $2dp[j_{2}+1], 3dp[j_{3}+1], 5dp[j_{5}+1]$ 谁更小即可,若 $2dp[j_{2}+1]$ 最小,则 $dp[i] = 2dp[j_{2}+1]$,然后将 $j_{2}$ 增加 1,推导后续状态时,$j_{2}$ 依然可以直接用。$3dp[j_{3}+1], 5dp[j_{5}+1]$ 最小时,处理方法类似。

基于上述决策单调性的性质,在推导状态 $dp[i]$ 时,决策候选集中就只有 $j_{2}+1, j_{3}+1, j_{5}+1$ 这三个数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 1;
int i2 = 0;
int i3 = 0;
int i5 = 0;
for(int i = 2; i <= n; ++i)
{
dp[i] = min(dp[i], dp[i2 + 1] * 2);
dp[i] = min(dp[i], dp[i3 + 1] * 3);
dp[i] = min(dp[i], dp[i5 + 1] * 5);
if(dp[i] == dp[i2 + 1] * 2)
++i2;
if(dp[i] == dp[i3 + 1] * 3)
++i3;
if(dp[i] == dp[i5 + 1] * 5)
++i5;
}
return dp[n];
}
};

Share