摘要: 子序列的枚举与顺序无关
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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 <= n == nums.length <= 50 |
题解
算法:动态规划
长为 n 的数组,长度为 k 的子序列共有 (nk) 种,我们要求的是这么多子序列的能量的和。
一个序列的能量的定义是任意两个元素的差值绝对值的最小值,而这个最小值只会出现在排序后相邻元素中,这个性质为我们寻找最优子结构提供了启发。
阶段
将原数组排序后,所有的子序列与排序之前是一样的,因此可以排序之后考虑问题。假设原数组已经从小到大排好序。然后按顺序考虑每一个元素。
假设当前考虑到元素 A[i],我们考虑如果选 A[i] 进入子序列,所有长为 k 的子序列的能量和,将其定义为 dp[i]。然后考虑下一个选入子序列的元素,也就是 A[i+1],⋯,A[n−1] 中,选谁作为子序列的下一个元素。
假设下一个元素选 A[x],x 可以取 i+1,⋯,n−1。我们要考虑的是如何通过 dp[x],x=i+1,⋯,n−1 的结果组装出 dp[i] 的结果。
由于子序列总长度为 k,因此我们需要知道 A[0],⋯,A[i−1] 中选入了多少个进入子序列,记其值为 j。也就是在 i 位置,我们考虑将 A 分为两部分,分别为 A[0],⋯,A[i−1] 以及 A[i],⋯,A[n−1]。j 表示前一部分已选入子序列的元素数,后一部分还需要选 k−j 个。由于 A[i] 需要选,因此 k−j>0,此外还需要满足 k−j≤n−i。
附加信息
有了以上信息后,可以将状态定义为 dp[i][j] 表示此前已经选入子序列 j 个元素,在 A[i],⋯,A[n−1] 中选 k−j 个元素,且 A[i] 需要选的情况下,所有可能的子序列的能量和。这样的话,当 k−j=0 或 k−j>n−1 时,d[i][j]=0。答案为 n−1∑i=0dp[i][0]。在当前状态 (i,j),可能的决策(也就是下一个加入子序列的元素)为 t=i+1,⋯,n−1,对应地状态转移到 (t,j+1)。
但此时根据 dp[t][j+1],t=i+1,⋯,n−1 还是不好组装出 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[n−1] 中选择 k−j 个元素,其中 A[i] 必须选,所得的所有可能的子序列的能量和。
这样定义的话,答案为 n−1∑i=0dp[i][0][INF]。
初始值有三块,一个是 j=k 时 dp[i][j][d]=0,另一个是 k−j>n−i 时,dp[i][j][d]=0,最关键的一个是当 j=k−1 时的情况,此时 A[0],⋯,A[i−1] 已经选了 k−1 个,再加上 A[i],刚好选了 k 个,此时该子序列的能量为 d,即 dp[i][j][d]=d。
状态转移方程
dp[i][j][d]=n−1∑t=i+1dp[t][j+1][min代码 (Python)
1 | from functools import lru_cache |