Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

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

  |  

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

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


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

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

题目

给你一个长度为 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 的子序列共有 (nk) 种,我们要求的是这么多子序列的能量的和。

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

阶段

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

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

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

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

附加信息

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

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

  • A[t]A[i]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],,A[n1] 中选择 kj 个元素,其中 A[i] 必须选,所得的所有可能的子序列的能量和。

这样定义的话,答案为 n1i=0dp[i][0][INF]

初始值有三块,一个是 j=kdp[i][j][d]=0,另一个是 kj>ni 时,dp[i][j][d]=0,最关键的一个是当 j=k1 时的情况,此时 A[0],,A[i1] 已经选了 k1 个,再加上 A[i],刚好选了 k 个,此时该子序列的能量为 d,即 dp[i][j][d]=d

状态转移方程

dp[i][j][d]=n1t=i+1dp[t][j+1][min

代码 (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
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

Share