动态规划的难点，找到最优子结构：排序后再尝试各种额外信息

字数统计: 1.5k字 | 阅读时长: 6分

2024-07-26

摘要: 子序列的枚举与顺序无关

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

各位好，今天我们来看一个动态规划的困哪题，主要难点还是如何发现最优子结构。

本题是在经过排序之后，进一步尝试各种额外信息，才艰难地找到最优子结构。额外信息的引入需要一些灵感和猜想，思考过程均在题解中。

题目

3098. 求出所有子序列的能量和

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个子序列的能量定义为子序列中任意两个元素的差值绝对值的最小值。

请你返回 nums 中长度等于 k 的所有子序列的能量和。

由于答案可能会很大，将答案对 109 + 7 取余后返回。

示例 1：
输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

示例 2：
输入：nums = [2,2], k = 2
输出：0
解释：
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。

示例 3：
输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。

提示：

1
2
3

2 <= n == nums.length <= 50
-108 <= nums[i] <= 1e8 
2 <= k <= n

题解

算法：动态规划

长为 $n$ 的数组，长度为 $k$ 的子序列共有 $\binom{n}{k}$ 种，我们要求的是这么多子序列的能量的和。

一个序列的能量的定义是任意两个元素的差值绝对值的最小值，而这个最小值只会出现在排序后相邻元素中，这个性质为我们寻找最优子结构提供了启发。

阶段

将原数组排序后，所有的子序列与排序之前是一样的，因此可以排序之后考虑问题。假设原数组已经从小到大排好序。然后按顺序考虑每一个元素。

假设当前考虑到元素 $A[i]$，我们考虑如果选 $A[i]$ 进入子序列，所有长为 $k$ 的子序列的能量和，将其定义为 $dp[i]$。然后考虑下一个选入子序列的元素，也就是 $A[i+1],\cdots,A[n-1]$ 中，选谁作为子序列的下一个元素。

假设下一个元素选 $A[x]$，$x$ 可以取 $i+1, \cdots, n-1$。我们要考虑的是如何通过 $dp[x], x = i+1, \cdots, n-1$ 的结果组装出 $dp[i]$ 的结果。

由于子序列总长度为 $k$，因此我们需要知道 $A[0],\cdots,A[i-1]$ 中选入了多少个进入子序列，记其值为 $j$。也就是在 $i$ 位置，我们考虑将 $A$ 分为两部分，分别为 $A[0],\cdots,A[i-1]$ 以及 $A[i], \cdots, A[n-1]$。$j$ 表示前一部分已选入子序列的元素数，后一部分还需要选 $k-j$ 个。由于 $A[i]$ 需要选，因此 $k - j > 0$，此外还需要满足 $k - j \leq n - i$。

附加信息

有了以上信息后，可以将状态定义为 $dp[i][j]$ 表示此前已经选入子序列 $j$ 个元素，在 $A[i],\cdots,A[n-1]$ 中选 $k-j$ 个元素，且 $A[i]$ 需要选的情况下，所有可能的子序列的能量和。这样的话，当 $k-j=0$ 或 $k-j > n-1$ 时，$d[i][j] = 0$。答案为 $\sum\limits_{i=0}\limits^{n-1}dp[i][0]$。在当前状态 $(i, j)$，可能的决策（也就是下一个加入子序列的元素）为 $t=i+1,\cdots,n-1$，对应地状态转移到 $(t,j+1)$。

但此时根据 $dp[t][j+1], t=i+1,\cdots,n-1$ 还是不好组装出 $dp[i][j]$。因为 $A[t] - A[i]$ 与 $A[0],\cdots,A[i]$ 中已选入子序列的元素的最近距离的大小关系对 $dp[t][j+1]$ 的计算有影响，因此我们还需要一个信息，即此前已经选入子序列的元素的最近距离，记其为 $d$。这样在 $(i, j, d)$ 状态，选择 $A[t]$ 作为下一步的决策，状态转移情况如下：

若 $A[t] - A[i] \geq d$，则转移到 $(t, j + 1, d)$；
若 $A[t] - A[i] < d$，则转移到 $(t, j + 1, A[t] - A[i])$。

至此，我们终于找到了最优子结构。

状态表示

定义 $dp[i][j][d]$ 表示此前已经选了 $j$ 个元素进入子序列，其中距离最近的一对元素的距离为 $d$，在 $A[i],\cdots,A[n-1]$ 中选择 $k-j$ 个元素，其中 $A[i]$ 必须选，所得的所有可能的子序列的能量和。

这样定义的话，答案为 $\sum\limits_{i=0}\limits^{n-1}dp[i][0][INF]$。

初始值有三块，一个是 $j=k$ 时 $dp[i][j][d] = 0$，另一个是 $k-j > n - i$ 时，$dp[i][j][d] = 0$，最关键的一个是当 $j=k-1$ 时的情况，此时 $A[0],\cdots,A[i-1]$ 已经选了 $k-1$ 个，再加上 $A[i]$，刚好选了 $k$ 个，此时该子序列的能量为 $d$，即 $dp[i][j][d] = d$。

状态转移方程

$dp[i][j][d] = \sum\limits_{t=i+1}\limits^{n-1}dp[t][j+1][\min(d, A[t] - A[i])]$

代码 (Python)

from functools import lru_cache

MOD = int(1e9 + 7)

class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        INF = nums[-1] - nums[0]

        @lru_cache(int(1e8))
        def solve(i: int , j: int, d: int) -> int:
            if j == k:
                return 0
            if k - j > n - i:
                return 0
            if j + 1 == k:
                return d
            r = 0
            for t in range(i + 1, n):
                r = (r + solve(t, j + 1, min(d, nums[t] - nums[i]))) % MOD
            return r

        ans = 0
        for i in range(n):
            ans = (ans + solve(i, 0, INF)) % MOD
        return ans

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法动态规划