手机网站建设设计,中国建设银行网站客户注册码,wordpress 件康,做快递网站难吗本文涉及知识点
动态规划 状态机dp 性能优化
LeetCode3098. 求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。 请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和…本文涉及知识点
动态规划 状态机dp 性能优化
LeetCode3098. 求出所有子序列的能量和
给你一个长度为 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 。
提示 2 n nums.length 50 -108 nums[i] 108 2 k n
动态规划状态机dp)初版
动态规划的状态 表示
pre 表示已经处理完前x个数组符合条件的数量,dp表示已经处理完x1数组符合条件的数量。
pre[i][j][end][len] 表示此子序列 a长度为len。 b,以nums[end]结束。 c,nums[j]-nums[i]的差最小。如果多个(i,j)符合条件取最小的。比如{1,2,3}的(I,j)是{0,1}而不是{1,2}。 空间复杂度O(nnnk) dp类似。
动态规划的转移方程
只需要从x 推导x1不需要推导x2,x3 ⋯ \cdots ⋯ 如果硬要的话需要用前缀和后缀和。 { d p p r e 不选择 n u m s [ x ] d p [ i ] [ j ] [ x ] [ l e n 1 ] . . . e l s e 且 n u m s [ j ] − n u m s [ i ] n u m s [ x ] − n u m s [ e n d ] d p [ e n d ] [ x ] [ x ] [ l e n 1 ] . . . e l s e \begin{cases} dp pre 不选择nums[x] \\ dp[i][j][x][len1] ... else 且 nums[j]-nums[i] nums[x]-nums[end] \\ dp[end][x][x][len1] ... else \\ \end{cases} ⎩ ⎨ ⎧dppredp[i][j][x][len1]...dp[end][x][x][len1]...else不选择nums[x]else且nums[j]−nums[i]nums[x]−nums[end] 时间复杂度O(nnnkn) 估计超时 剪枝 枚举的时候确保 i j 且 j x。
动态规划前缀和
拆分成若干个子问题假定序列存在(i,j)且此序列的能力为power nums[j]-nums[i]。
动态规划的状态表示
dp[len][end] 表示 子序列的长度为len最后一个元素是end。 空间复杂度O(kn)
利用前缀和优化 动态规划的转移方程
枚举endend not ∈ \in ∈(i,j) 否则此序列的能量就不是nums[j]-nums[i]了。 { o l d E n d ∈ [ 0 , e n d ) 且 n u m s [ e n d ] − n u m s [ o l d E n d ] p o w e r e n d i o e d E n d ∈ ( e n d , n ) 且 n u m s [ e n d ] − n u m s [ o l d E n d ] p o w e r e n d j \begin{cases} oldEnd \in [0,end)且nums[end] -nums[oldEnd] power end i \\ oedEnd \in (end,n) 且 nums[end] -nums[oldEnd] power end j \\ \end{cases} {oldEnd∈[0,end)且nums[end]−nums[oldEnd]poweroedEnd∈(end,n)且nums[end]−nums[oldEnd]powerendiendj
如果不利用前缀和优先时间复杂度O(knn)利用前缀和优化O(kn)。 总时间复杂度O(knkn)。
动态规划的初始状态
枚举所有长度为2
动态规划的填表顺序 l e n 3 n _{len3}^{n} len3n
动态规划的返回值
len k 且 end j 才是需要统计的子序列数量。
代码
没用前缀和优化
理论上过不了实际过了。
templateint MOD 1000000007
class C1097Int
{
public:C1097Int(long long llData 0) :m_iData(llData% MOD){}C1097Int operator(const C1097Int o)const{return C1097Int(((long long)m_iData o.m_iData) % MOD);}C1097Int operator(const C1097Int o){m_iData ((long long)m_iData o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){m_iData (m_iData MOD - o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){return C1097Int((m_iData MOD - o.m_iData) % MOD);}C1097Int operator*(const C1097Int o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int operator*(const C1097Int o){m_iData ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator(const C1097Int o)const{return m_iData o.m_iData;}bool operator(const C1097Int o)const{return m_iData o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet 1, iCur *this;while (n){if (n 1){iRet * iCur;}iCur * iCur;n 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData 0;;
};class Solution {
public:int sumOfPowers(vectorint nums, const int K) {m_c nums.size();sort(nums.begin(), nums.end()); C1097Int biRet 0;for (int i 0; i m_c; i) {for (int j i 1; j m_c; j) {auto cur Do(nums, i, j, K);biRet cur;//std::cout i : i j: j cur.ToInt() std::endl;}}return biRet.ToInt();}C1097Int Do(const vectorint nums,int i,int j, const int K) {const int iDiff nums[j] - nums[i];vectorvectorC1097Int dp(K 1, vectorC1097Int(m_c));for (int end 0; end i; end) {for (int end1 0; end1 end; end1) {if (nums[end] - nums[end1] iDiff) {dp[2][end] 1;}}}dp[2][j] 1;for (int len 3; len K; len) {for (int end 0; end i; end) {for (int end1 0; end1 end; end1) {if (nums[end] - nums[end1] iDiff) {dp[len][end] dp[len - 1][end1];}}}dp[len][j] dp[len - 1][i];for (int end j1; end m_c; end) {for (int end1 j; end1 end; end1) {if (nums[end] - nums[end1] iDiff) {dp[len][end] dp[len - 1][end1];}}}}return std::accumulate(dp.back().begin() j, dp.back().end(), C1097Int())*iDiff;}int m_c;
};测试用例
int main()
{vectorint nums;int k;{Solution sln;nums { 6,14,4,13 }, k 3;auto res sln.sumOfPowers(nums, k);Assert(6, res);}{Solution sln;nums { 1,2,3,4 }, k 3;auto res sln.sumOfPowers(nums, k);Assert(4, res);}{Solution sln;nums { 4,3,-1 }, k 2;auto res sln.sumOfPowers(nums, k);Assert(10, res);}{Solution sln;nums { 2,2 }, k 2;auto res sln.sumOfPowers(nums, k);Assert(0, res);}{Solution sln;nums { 2,246006,496910,752786,1013762,1279948,1551454,1828436,2110982,2399316,2693558,2993942,3300640,3613766,3933442,4259696,4592656,4932556,5279494,5633522,5994678,6363102,6739028,7122528,7513792,7913044,8320394,8736004,9160062,9592750,10034184,10484602,10944108,11412852,11891048,12378822,12876346,13383746,13901098,14428528,14966126,15514010,16072380,16641300,17220904,17811360,18412850,19025600,19649778,20285440 }, k 37;auto res sln.sumOfPowers(nums, k);Assert(273504325, res);}
}利用前缀和优化用时减少不到50%
templateint MOD 1000000007
class C1097Int
{
public:C1097Int(long long llData 0) :m_iData(llData% MOD){}C1097Int operator(const C1097Int o)const{return C1097Int(((long long)m_iData o.m_iData) % MOD);}C1097Int operator(const C1097Int o){m_iData ((long long)m_iData o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){m_iData (m_iData MOD - o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){return C1097Int((m_iData MOD - o.m_iData) % MOD);}C1097Int operator*(const C1097Int o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int operator*(const C1097Int o){m_iData ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator(const C1097Int o)const{return m_iData o.m_iData;}bool operator(const C1097Int o)const{return m_iData o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet 1, iCur *this;while (n){if (n 1){iRet * iCur;}iCur * iCur;n 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData 0;;
};class Solution {
public:int sumOfPowers(vectorint nums, const int K) {m_c nums.size();sort(nums.begin(), nums.end());C1097Int biRet 0;for (int i 0; i m_c; i) {for (int j i 1; j m_c; j) {auto cur Do(nums, i, j, K);biRet cur;//std::cout i : i j: j cur.ToInt() std::endl;}}return biRet.ToInt();}C1097Int Do(const vectorint nums, int i, int j, const int K) {const int iDiff nums[j] - nums[i];vectorvectorC1097Int dp(K 1, vectorC1097Int(m_c));for (int end 0; end i; end) {for (int end1 0; end1 end; end1) {if (nums[end] - nums[end1] iDiff) {dp[2][end] 1;}}}dp[2][j] 1;for (int len 3; len K; len) {int end1 0;C1097Int biRet 0;for (int end 0; end i; end) {while ((end1 end) (nums[end] - nums[end1] iDiff)) {biRet dp[len - 1][end1];end1;}dp[len ][end] biRet;}dp[len][j] dp[len - 1][i];C1097Int biRet2 0;for (int end j 1,end1j ; end m_c; end) {while ((end1 end) (nums[end] - nums[end1] iDiff)) {biRet2 dp[len - 1][end1];end1;}dp[len][end] biRet2;}}return std::accumulate(dp.back().begin() j, dp.back().end(), C1097Int()) * iDiff;}int m_c;
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
