算法动态规划

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

字数统计: 2.1k字   |   阅读时长: 8分
, ,

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

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