【leetcode刷题】动态规划 Part 5 划分型DP

我们今天来复习一下第5部分：划分型DP

因为有6道题太难了做不出来，后面会补上

132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

Solution

这题主要是介绍一下划分型DP的常见解法，以及回文串预处理的方式。
划分型DP通常分为三种，能否划分、最优划分、以及约束划分
最优划分，就是着重求最少/最多划分次数
约束划分，就是给定划分次数，然后计算有关划分后子数组的相关值
本题属于最优划分，也就是求最少划分次数。
这种题我们通常设\(dp[i]\)为前\(i\)个元素能够被划分出的最小/最大组数，然后递推求解。
然后本题还要介绍的知识点就是有关回文串预处理的方式。
为了记录结果，我们通常使用动态规划，当然还有所谓的\(Manacher\)算法，这个在后面刷字符串题的时候再介绍。

class Solution {
public:int minCut(string s) {int n=s.length();const int INF=1e9+7;   vector<vector<int>>ma(n+5,vector<int>(n+5,false));for(int i=0;i<=n-1;i++){for(int j=i;j>=0;j--){if(s[j]==s[i]&&(i-j<=1||(ma[j+1][i-1]&&i-j>=2))) ma[j][i]=true;}}vector<int>dp(n+6,INF);dp[0]=0;for(int i=0;i<=n-1;i++){if(ma[0][i]){dp[i]=0;continue;}for(int j=0;j<=i-1;j++){if(ma[j+1][i]) dp[i]=min(dp[i],dp[j]+1);}}return dp[n-1];}
};

3196. 最大化子数组的总成本

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

子数组 nums[l..r]（其中 0 <= l <= r < n）的 成本 定义为：

\[cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)^{r − l} \]

你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。

具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 \(i_1, i_2, ..., i_{k − 1}\)（其中 \(0 <= i_1 < i_2 < \ldots < i_{k - 1} < n - 1\)），则总成本为：

\[cost(0, i_1) + cost(i_1 + 1, i_2) + ... + cost(i_{k − 1} + 1, n − 1) \]

返回在最优分割方式下的子数组成本之和的最大值。

注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。

示例 1：

输入： nums = [1,-2,3,4]
输出： 10
解释：
一种总成本最大化的方法是将 [1, -2, 3, 4] 分割成子数组 [1, -2, 3] 和 [4]。总成本为 (1 + 2 + 3) + 4 = 10。

示例 2：

输入： nums = [1,-1,1,-1]
输出： 4
解释：
一种总成本最大化的方法是将 [1, -1, 1, -1] 分割成子数组 [1, -1] 和 [1, -1]。总成本为 (1 + 1) + (1 + 1) = 4。

示例 3：

输入： nums = [0]
输出： 0
解释：
无法进一步分割数组，因此答案为 0。

示例 4：

输入： nums = [1,-1]
输出： 2
解释：
选择整个数组，总成本为 1 + 1 = 2，这是可能的最大成本。

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Solution

这道题我们要介绍式子变形的思想，这个思想在后面的题目中会多处用到。
你看那个式子，它由交叉级数组成，那么，我们是不是可以将其化简为1项与2项交叉之和？
然后这题的转移方程就能算出来了

class Solution {
public:long long maximumTotalCost(vector<int>& nums) {int n=nums.size();const long long INF=1e18;vector<long long>dp(n+5,-INF);if(n==1) return nums[0];dp[0]=nums[0],dp[1]=max(nums[0]+nums[1],nums[0]-nums[1]);if(n==1||n==2) return dp[n-1];for(int i=2;i<=n-1;i++){long long tem1=dp[i-2]+nums[i-1]-nums[i];long long tem2=dp[i-1]+nums[i];dp[i]=max(tem1,tem2);}return dp[n-1];}
};

2472. 不重叠回文子字符串的最大数目

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 k 。
• 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

示例 1 ：

输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。

提示：

• 1 <= k <= s.length <= 2000
• s 仅由小写英文字母组成

Solution

这题开始，我们要介绍前缀和优化DP这个概念，这个在本期中会反复出现
首先，我们预处理这个回文串，然后我们写出朴素的转移方程

\[dp[i]=max\{dp[j-1]+1\} \ if \ ma[j-1][i-1]==true \]

由于\(dp[i]\)在形成后就不再改变了，我们可以用一个前缀和数组记录\(dp\)的前缀最大值
随后就直接更新DP数组，有以下转移方程

\[dp[i]=pre[j-1]+1 \ if \ ma[j-1][i-1]==true \]

class Solution {
public:int maxPalindromes(string s, int k) {int l=s.length();vector<vector<bool>>ma(l+5,vector<bool>(l+5,false));for(int i=0;i<=l-1;i++){for(int j=i;j>=0;j--){if(s[j]==s[i]&&(i-j<=1||ma[j+1][i-1])){ma[j][i]=true;}}}vector<int>dp(l+5,0);for(int i=k;i<=l;i++){vector<int>pre(i-k+5,0);for(int j=1;j<=i-k+1;j++){pre[j]=max(pre[j-1],dp[j]);}for(int j=i-k+1;j>=1;j--){if(ma[j-1][i-1]){dp[i]=max(dp[i],pre[j-1]+1);}}}int ans=0;for(int i=1;i<=l;i++) ans=max(ans,dp[i]);return ans;}
};

2547. 拆分数组的最小代价

给你一个整数数组 nums 和一个整数 k 。
将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。

• 例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。

子数组的 重要性 定义为 k + trimmed(subarray).length 。

• 例如，如果一个子数组是 [1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。

找出并返回拆分 nums 的所有可行方案中的最小代价。
子数组 是数组的一个连续 非空 元素序列。

示例 1：

输入：nums = [1,2,1,2,1,3,3], k = 2
输出：8
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3]
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。
拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 2：

输入：nums = [1,2,1,2,1], k = 2
输出：6
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1] 。
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1] 的重要性是 2 + (2) = 4 。
拆分的代价是 2 + 4 = 6 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 3：

输入：nums = [1,2,1,2,1], k = 5
输出：10
解释：将 nums 拆分成一个子数组：[1,2,1,2,1].
[1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。
拆分的代价是 10 ，可以证明这是所有可行的拆分方案中的最小代价。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < nums.length
• 1 <= k <= 109

Solution

这题的预处理按照map来模拟即可

3578. 统计极差最大为 K 的分割方式数

给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。

返回在此条件下将 nums 分割的总方法数。

由于答案可能非常大，返回结果需要对 \(10^9 + 7\) 取余数。

示例 1：

输入： nums = [9,4,1,3,7], k = 4
输出： 6
解释：
共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：

• [ [9], [4], [1], [3], [7] ]
• [ [9], [4], [1], [3, 7] ]
• [ [9], [4], [1, 3], [7] ]
• [ [9], [4, 1], [3], [7]]
• [ [9], [4, 1], [3, 7] ]
• [ [9], [4, 1, 3], [7] ]

示例 2：

输入： nums = [3,3,4], k = 0
输出： 2
解释：
共有 2 种有效的分割方式，满足给定条件：

• [ [3], [3], [4] ]
• [ [3, 3], [4] ]

提示：

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

Solution

这道题我们肯定是需要优化的，数据太大了
所以，怎么优化？我们要知道，维护一个数组的最大值和最小值，肯定是用单调队列更加方便。
所以，这道题就是单调队列优化DP的题目
我们现在要做的就是，考虑入队和出队条件
因为要优化的一定是原来的反向遍历这一项，队列里的元素应该是原数组下标或者原数组元素。
然后，要考虑出队条件，是什么？就是队头（最早、最小/大）的，要直接出队，知道满足非空或者题目中条件。
因此，存储原数组下标更方便我们进行更新。
另外，既然只有一维递推，那么前缀和优化又要派生用场了。
挂个中等真的太坑了

class Solution {
public:int countPartitions(vector<int>& nums, int k) {int n=nums.size();const int INF=1e9+7;deque<int>q1,q2;//q1表最大值队列，q2表示最小值队列vector<int>pre(n+5,0);vector<int>dp(n+5,0);dp[0]=1;pre[0]=1;int l=0;for(int i=1;i<=n;i++){int x=nums[i-1];while(!q1.empty()&&x>=nums[q1.back()]) q1.pop_back();while(!q2.empty()&&x<=nums[q2.back()]) q2.pop_back();q1.push_back(i-1),q2.push_back(i-1);while(!q1.empty()&&!q2.empty()&&nums[q1.front()]-nums[q2.front()]>k){if(l==q1.front()) q1.pop_front();if(l==q2.front()) q2.pop_front();l++;}if(l>0) dp[i]=(pre[i-1]-pre[l-1]+INF)%INF;else dp[i]=pre[i-1]%INF;pre[i]=(pre[i-1]+dp[i])%INF;}return dp[n];}
};

2430. 对字母串可执行的最大删除数

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

• 删除 整个字符串 s ，或者
• 对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。

例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab"; 。

返回删除 s 所需的最大操作数。

示例 1：

输入：s = "abcabcdabc"
输出：2
解释：

• 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
• 删除全部字母。
  一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
  注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。

示例 2：

输入：s = "aaabaab"
输出：4
解释：

• 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
• 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。
• 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
• 删除全部字母。
  一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。

示例 3：

输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。

提示：

• 1 <= s.length <= 4000
• s 仅由小写英文字母组成

Solution

本题的问题是，怎么在O(n^2)之内预处理出两个字符串的关系
答案，字符串哈希！
我们把一个字符串看成P(某个大质数)进制数，然后利用unsigned long long的自动溢出特性，进行比对。

class Solution {
public:int deleteString(string s) {int l=s.length();const unsigned long long P=131;vector<vector<bool>>ma(l+5,vector<bool>(l+5,false));vector<unsigned long long>pre(l+5,0);vector<unsigned long long>ha(l+5,0);pre[0]=1;for(int i=1;i<=l;i++){ha[i]=ha[i-1]*P+(s[i-1]-'a'+1);pre[i]=pre[i-1]*P;}vector<int>dp(l+5,0);for(int i=l;i>=1;i--){dp[i]=max(1,dp[i]);for(int j=i+1;j<=l;j+=2){if(ha[(j+i-1)/2]-ha[i-1]*pre[(j-i+1)/2]==ha[j]-ha[(j+i-1)/2]*pre[(j-i+1)/2]){dp[i]=max(dp[(i+j+1)/2]+1,dp[i]);}}}return dp[1];}
};

3579. 字符串转换需要的最小操作数

给你两个长度相等的字符串 word1 和 word2。你的任务是将 word1 转换成 word2。

为此，可以将 word1 分割成一个或多个连续子字符串。对于每个子字符串 substr，可以执行以下操作：

1. 替换：将 substr 中任意一个索引处的字符替换为另一个小写字母。

2. 交换：交换 substr 中任意两个字符的位置。

3. 反转子串：将 substr 进行反转。

每种操作计为 一次 ，并且每个子串中的每个字符在每种操作中最多只能使用一次（即任何字符的下标不能参与超过一次替换、交换或反转操作）。

返回将 word1 转换为 word2 所需的 最小操作数 。

子串 是字符串中任意一个连续且非空的字符序列。

示例 1：

输入： word1 = "abcdf", word2 = "dacbe"
输出： 4
解释：
将 word1 分割为 "ab"、"c" 和 "df"。操作如下：

• 对于子串 "ab"：
  • 执行类型 3 的操作："ab" -> "ba"。
  • 执行类型 1 的操作："ba" -> "da"。
• 对于子串 "c"：无需操作。
• 对于子串 "df"：
  • 执行类型 1 的操作："df" -> "bf"。
  • 执行类型 1 的操作："bf" -> "be"。

示例 2：

输入： word1 = "abceded", word2 = "baecfef"
输出： 4
解释：
将 word1 分割为 "ab"、"ce" 和 "ded"。操作如下：

• 对于子串 "ab"：
  • 执行类型 2 的操作："ab" -> "ba"。
• 对于子串 "ce"：
  • 执行类型 2 的操作："ce" -> "ec"。
• 对于子串 "ded"：
  • 执行类型 1 的操作："ded" -> "fed"。
  • 执行类型 1 的操作："fed" -> "fef"。

示例 3：

输入： word1 = "abcdef", word2 = "fedabc"
输出： 2
解释：

将 word1 分割为 "abcdef"。操作如下：

• 对于子串 "abcdef"：
  • 执行类型 3 的操作："abcdef" -> "fedcba"。
  • 执行类型 2 的操作："fedcba" -> "fedabc"。

提示：

• 1 <= word1.length == word2.length <= 100
• word1 和 word2 仅由小写英文字母组成。

Solution

本题的难点在于，如何在给定的时间复杂度内进行预处理
我们对于一段字符串，考虑一对字符\((s_i,t_i)\)，表示在word1中出现了\(s_i\)，同样下标内在word2中出现了\(t_i\)的数对数量
那么得出，如果可以调换，那么必然存在\([s_i][t_i]\)与\([t_i][s_i]\)都大于0的情况
反转也同理，我们可以先反转，然后再进行同样的处理

class Solution {
public:int minOperations(string word1, string word2) {int l=word1.length();const int INF=1e9+7;vector<vector<int>>ma(l+5,vector<int>(l+5,0));for(int i=0;i<=l-1;i++){for(int j=i;j<=l-1;j++){int cnt[26][26]{0};int op=0,rop=1;for(int k=i;k<=j;k++){int x=word1[k]-'a',y=word2[k]-'a';if(x==y) continue;if(cnt[y][x]>0){cnt[y][x]--;continue;}cnt[x][y]++;op++;}int rcnt[26][26]{0};for(int k=0;k<=j-i;k++){int x=word1[i+k]-'a',y=word2[j-k]-'a';if(x==y) continue;if(rcnt[y][x]>0){rcnt[y][x]--;continue;}rcnt[x][y]++;rop++;}ma[i][j]=min(op,rop);}}vector<int>dp(l+5,INF);dp[0]=0;for(int i=1;i<=l;i++){for(int j=i;j>=1;j--){dp[i]=min(dp[i],dp[j-1]+ma[j-1][i-1]);}}return dp[l];}
};

2463. 最小移动总距离

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 \(factory[j] = [position_j, limit_j]\) ，表示第 j 个工厂的位置在 \(position_j\) ，且第 j 个工厂最多可以修理 \(limit_j\) 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

• 所有机器人移动速度相同。
• 如果两个机器人移动方向相同，它们永远不会碰撞。
• 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
• 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
• 机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

示例 1：

输入：robot = [0,4,6], factory = [ [2,2],[6,2] ]
输出：4
解释：如上图所示：

• 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
• 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
• 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
  第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
  第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
  总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [ [-2,1],[2,1] ]
输出：2
解释：如上图所示：

• 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
• 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
  第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
  第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
  总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

提示：

• 1 <= robot.length, factory.length <= 100
• factory[j].length == 2
• \(-10^9 <= robot[i], position_j <= 10^9\)
• \(0 <= limit_j <= robot.length\)
• 测试数据保证所有机器人都可以被维修。

Solution

首先，我们肯定是要把机器人跟工厂的位置排个序的，然后，我们也容易看出这道题是个分组题
提醒：外层可以枚举工厂而非机器人，这样会更利于理解，也更方便，想不出来的时候可以想想状态设计是不是少了维度或者枚举的顺序不对，这在我们后面的约束划分中也会出现。

class Solution {
public:long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {int n=robot.size(),m=factory.size();const long long INF=2e17;vector<vector<long long>>dp(m+5,vector<long long>(n+5,INF));sort(robot.begin(),robot.end());sort(factory.begin(),factory.end(),[](const vector<int> &x,const vector<int> &y){ return x[0]<y[0]; });for(int i=0;i<=m;i++) dp[i][0]=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){ dp[i][j]=min(dp[i][j],dp[i-1][j]);long long cost=0;for(int k=1;k<=min(factory[i-1][1],j);k++){cost+=abs((long long)robot[j-k]-(long long)factory[i-1][0]);dp[i][j]=min(dp[i][j],dp[i-1][j-k]+cost);}}}return dp[m][n];}
};

3500. 将数组分割为子数组的最小代价

给你两个长度相等的整数数组 nums 和 cost，和一个整数 k。

你可以将 nums 分割成多个子数组。第 i 个子数组由元素 nums[l..r] 组成，其代价为：

• (nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r])。

注意，i 表示子数组的顺序：第一个子数组为 1，第二个为 2，依此类推。

返回通过任何有效划分得到的 最小 总代价。

子数组 是一个连续的 非空 元素序列。

示例 1：

输入： nums = [3,1,4], cost = [4,6,6], k = 1
输出： 110
解释：
将 nums 分割为子数组 [3, 1] 和 [4] ，得到最小总代价。

• 第一个子数组 [3,1] 的代价是 (3 + 1 + 1 * 1) * (4 + 6) = 50。
• 第二个子数组 [4] 的代价是 (3 + 1 + 4 + 1 * 2) * 6 = 60。

示例 2：

输入： nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
输出： 985
解释：
将 nums 分割为子数组 [4, 8, 5, 1] ，[14, 2, 2] 和 [12, 1] ，得到最小总代价。

• 第一个子数组 [4, 8, 5, 1] 的代价是 (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525。
• 第二个子数组 [14, 2, 2] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250。
• 第三个子数组 [12, 1] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210。

提示：

• 1 <= nums.length <= 1000
• cost.length == nums.length
• 1 <= nums[i], cost[i] <= 1000
• 1 <= k <= 1000

Solution

启发：当题目给了我们一个很复杂的式子的时候，有没有办法可以化简？
以这题的式子为例，$$(nums_0+nums_1+ \ldots nums_{r}+k \times i) \times (cost_{l}+cost{l+1}+\ldots +cost_{r})$$
我们不妨将前面的\(nums\)部分化简为已分组的部分，则有$$(sum_1+sum_2+\ldots+sum_{i}+k \times i) \times cost_{i}$$
也就是$$((sum_1+k)+(sum_2+k)+\ldots+(sum_i+k)) \times cost_{i}$$
累加后发现，全部的代价就是$$(sum_1+k) \times costs + (sum_2+k) \times (costs-cost_2) + \ldots (sum_i+k) \times (costs-cost_1- \ldots-cost_{i-1}) \ ，其中costs=\sum\limits_{i=1}^{n}cost[i]$$
然后就可以用前缀和算出来了，记得开long long与强转

class Solution {
public:long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {int n=nums.size();const long long INF=1e18;vector<long long>prenums(n+5,0);for(int i=1;i<=n;i++) prenums[i]=prenums[i-1]+nums[i-1];vector<long long>precost(n+5,0);for(int i=1;i<=n;i++) precost[i]=precost[i-1]+cost[i-1];vector<long long>dp(n+5,INF);dp[0]=0;for(int i=1;i<=n;i++){for(int j=i;j>=1;j--){dp[i]=min(dp[i],dp[j-1]+(prenums[i]-prenums[j-1]+k)*(precost[n]-precost[j-1]));}}return dp[n];}
};

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。

返回分割后最小的和的最大值。

子数组 是数组中连续的部份。

示例 1：

输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], k = 2
输出：9

示例 3：

输入：nums = [1,4,4], k = 3
输出：4

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Solution

这道题就是我们之前说的约束划分的典题，通常的解决方法是用\(dp[i][j]\)表示前\(j\)个元素被划分为\(i\)组的最优解

class Solution {
public:int splitArray(vector<int>& nums, int k) {int n=nums.size();const int INF=2e9+7;vector<int>pre(n+5,0);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+nums[i-1];vector<vector<int>>dp(k+5,vector<int>(n+5,INF));for(int i=0;i<=k;i++) dp[i][0]=0;for(int i=1;i<=k;i++){for(int j=i;j<=n-(k-i);j++){for(int v=j-1;v>=i-1;v--){dp[i][j]=min(dp[i][j],max(dp[i-1][v],pre[j]-pre[v]));}}}return dp[k][n];}
};

1473. 粉刷房子 III

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

• houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
• cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

示例 1：

输入：houses = [0,0,0,0,0], cost = [ [1,10],[10,1],[10,1],[1,10],[5,1] ], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

输入：houses = [0,2,1,2,0], cost = [ [1,10],[10,1],[10,1],[1,10],[5,1] ], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

输入：houses = [0,0,0,0,0], cost = [ [1,10],[10,1],[1,10],[10,1],[1,10] ], m = 5, n = 2, target = 5
输出：5

示例 4：

输入：houses = [3,1,2,3], cost = [ [1,1,1],[1,1,1],[1,1,1],[1,1,1] ], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

• m == houses.length == cost.length
• n == cost[i].length
• 1 <= m <= 100
• 1 <= n <= 20
• 1 <= target <= m
• 0 <= houses[i] <= n
• 1 <= cost[i][j] <= 10^4

Solution

这道题看着其实不大好做，那么，我们就需要拓展一下DP数组的维度了
我们用\(dp[i][j][k]\)表示第\(i\)个房子被涂成颜色\(k\)时的最大值
然后就可以写出转移方程了，至于所谓的分区模板完全被必要套

class Solution {
public:int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {const int INF=2e9;vector<vector<vector<int>>>dp(m+5,vector<vector<int>>(n+5,vector<int>(m+5,INF)));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) dp[0][i][j]=0;}for(int i=1;i<=m;i++){if(houses[i-1]!=0){for(int j=1;j<=n;j++){for(int v=1;v<=i;v++){if(houses[i-1]==j) dp[i][j][v]=min(dp[i][j][v],dp[i-1][j][v]);else dp[i][houses[i-1]][v]=min(dp[i][houses[i-1]][v],dp[i-1][j][v-1]);}}continue;}for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){for(int v=1;v<=i;v++){if(j==k) dp[i][j][v]=min(dp[i][j][v],dp[i-1][j][v]+cost[i-1][j-1]);else dp[i][j][v]=min(dp[i][j][v],dp[i-1][k][v-1]+cost[i-1][j-1]);}}}}int ans=INF;for(int i=1;i<=n;i++) ans=min(ans,dp[m][i][target]);return ans==2e9?-1:ans;}
};

1478. 安排邮筒

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

示例 1：

输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例 2：

输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

示例 3：

输入：houses = [7,4,6,1], k = 1
输出：8

示例 4：

输入：houses = [3,6,14,10], k = 4
输出：0

提示：

• n == houses.length
• 1 <= n <= 100
• 1 <= houses[i] <= 10^4
• 1 <= k <= n
• 数组 houses 中的整数互不相同。

Solution

这次要介绍一个问题，就是所谓中位数贪心
也就是，对于一组数，要把其变成全部相等，所需步骤数最少的时候即为中位数时。
这题也差不多，知道这个道理了就差不多清楚了

class Solution {
public:int minDistance(vector<int>& houses, int k) {int n=houses.size();sort(houses.begin(),houses.end());const int INF=2e9;vector<vector<long long>>dp(n+5,vector<long long>(n+5,INF));for(int i=0;i<=n;i++) dp[0][i]=0;for(int i=1;i<=n;i++){int temp;for(int j=i;j>=1;j--){if((i-j+1)%2) temp=houses[(i+j)/2-1];else temp=(houses[(i+j)/2-1]+houses[(i+j)/2])/2;long long tem=0;for(int v=j;v<=i;v++){tem+=abs((long long)houses[v-1]-(long long)temp);}for(int v=1;v<=j;v++){dp[i][v]=min(dp[i][v],dp[j-1][v-1]+tem);}                }}return dp[n][k];}
};

3473. 长度至少为 M 的 K 个子数组之和

给你一个整数数组 nums 和两个整数 k 和 m。

返回数组 nums 中 k 个不重叠子数组的 最大 和，其中每个子数组的长度 至少 为 m。

子数组 是数组中的一个连续序列。

示例 1：

输入: nums = [1,2,-1,3,3,4], k = 2, m = 2
输出: 13
解释:
最优的选择是:

• 子数组 nums[3..5] 的和为 3 + 3 + 4 = 10（长度为 3 >= m）。
• 子数组 nums[0..1] 的和为 1 + 2 = 3（长度为 2 >= m）。

总和为 10 + 3 = 13。

示例 2：

输入: nums = [-10,3,-1,-2], k = 4, m = 1
输出: -10
解释:

最优的选择是将每个元素作为一个子数组。输出为 (-10) + 3 + (-1) + (-2) = -10。

提示:

• 1 <= nums.length <= 2000
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= floor(nums.length / m)
• 1 <= m <= 3

Solution

这题看到这个数据范围就得考虑优化了，我们写出转移方程

\[dp[i][j]=max\{dp[i][j-1],dp[i-1][v]+pre[j]-pre[v]\}, \ if \ (i-1)*m<=v<=j-m \]

我们发现\(dp[i-1][v]-pre[v]\)是一个前缀最大值，而\(pre[j]\)可以单独提出来
只需要单独维护这个最大值就可以了

class Solution {
public:int maxSum(vector<int>& nums, int k, int m) {int n=nums.size();const int INF=2e9;vector<int>pre(n+5,0);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+nums[i-1];vector<vector<int>>dp(n+5,vector<int>(n+5,-INF));for(int i=0;i<=n;i++) dp[i][0]=0;for(int i=1;i<=k;i++){int mx=-INF;for(int j=i*m;j<=n-(k-i)*m;j++){mx=max(mx,dp[j-m][i-1]-pre[j-m]);dp[j][i]=max(mx+pre[j],dp[j-1][i]);}}return dp[n][k];}
};

1959. K 次调整数组大小浪费的最小总空间

你正在设计一个动态数组。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 i 时刻数组中的元素数目。除此以外，你还有一个整数 k ，表示你可以 调整 数组大小的 最多 次数（每次都可以调整成 任意 大小）。

t 时刻数组的大小 \(size_t\) 必须大于等于 nums[t] ，因为数组需要有足够的空间容纳所有元素。t 时刻 浪费的空间 为 \(size_t - nums[t]\) ，总 浪费空间为满足 0 <= t < nums.length 的每一个时刻 t 浪费的空间 之和 。

在调整数组大小不超过 k 次的前提下，请你返回 最小总浪费空间 。

注意：数组最开始时可以为 任意大小 ，且 不计入 调整大小的操作次数。

示例 1：

输入：nums = [10,20], k = 0
输出：10
解释：size = [20,20].
我们可以让数组初始大小为 20 。
总浪费空间为 (20 - 10) + (20 - 20) = 10 。

示例 2：

输入：nums = [10,20,30], k = 1
输出：10
解释：size = [20,20,30].
我们可以让数组初始大小为 20 ，然后时刻 2 调整大小为 30 。
总浪费空间为 (20 - 10) + (20 - 20) + (30 - 30) = 10 。

示例 3：

输入：nums = [10,20,15,30,20], k = 2
输出：15
解释：size = [10,20,20,30,30].
我们可以让数组初始大小为 10 ，时刻 1 调整大小为 20 ，时刻 3 调整大小为 30 。
总浪费空间为 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15 。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 10^6
• 0 <= k <= nums.length - 1

Solution

先翻译题目：分成(k+1)组，然后每组的贡献为组内最大数与其他数的绝对值之差的和，求贡献的和最小值
我们写出转移方程

\[dp[i][j]=max{dp[i-1][v-1]+(max{nums[v]->nums[j]}*(j-v+1)-pre[j]+pre[v-1])} \]

然后就完事了

class Solution {
public:int minSpaceWastedKResizing(vector<int>& nums, int k) {int n=nums.size();vector<int>pre(n+5,0);for(int i=1;i<=n;i++) pre[i]=nums[i-1]+pre[i-1];const int INF=2e9;vector<vector<int>>dp(k+2,vector<int>(n+5,INF));dp[0][0]=0;for(int i=1;i<=k+1;i++){for(int j=i;j<=n-(k+1-i);j++){int mx=-INF;for(int v=j;v>=i;v--){mx=max(mx,nums[v-1]);dp[i][j]=min(dp[i][j],dp[i-1][v-1]+(mx*(j-v+1)-pre[j]+pre[v-1]));}}}return dp[k+1][n];}
};

2478. 完美分割的方案数

给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。

如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：

• s 被分成 k 段互不相交的子字符串。
• 每个子字符串长度都 至少 为 minLength 。
• 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。

请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 \(10^9 + 7\) 取余 后的结果。

一个 子字符串 是字符串中一段连续字符串序列。

示例 1：

输入：s = "23542185131", k = 3, minLength = 2
输出：3
解释：存在 3 种完美分割方案：
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"

示例 2：

输入：s = "23542185131", k = 3, minLength = 3
输出：1
解释：存在一种完美分割方案："2354 | 218 | 5131" 。

示例 3：

输入：s = "3312958", k = 3, minLength = 1
输出：1
解释：存在一种完美分割方案："331 | 29 | 58" 。

提示：

• 1 <= k, minLength <= s.length <= 1000
• s 每个字符都为数字 '1' 到 '9' 之一。

Solution

这道题一看就要优化了，我们先把转移方程写出来

\[dp[i][j]=\sum\limits_{v=(i-1)*minLength}^{j-minLength}dp[i-1][v] \ if \ true \]

然后我们发现，可以用前缀和维护
于是就有下面的代码:

class Solution {
public:bool isprime(char x){if(x=='2'||x=='3'||x=='5'||x=='7') return true;else return false;}int beautifulPartitions(string s, int k, int minLength) {int l=s.length();const int INF=1e9+7;vector<vector<int>>dp(k+3,vector<int>(l+5,0));if(!isprime(s[0])||isprime(s[l-1])) return 0; dp[0][0]=1;for(int i=1;i<=k;i++){int mx=0;for(int j=i*minLength;j<=l-(k-i)*minLength;j++){if(j==minLength||(j>minLength&&isprime(s[j-minLength]))){//如果开头符合条件mx+=dp[i-1][j-minLength]%INF;mx%=INF;}if(!isprime(s[j-1])){//如果结尾符合条件dp[i][j]+=mx;dp[i][j]%=INF;}}}return dp[k][l]%INF;}
};

3077. K 个不相交子数组的最大能量值

给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。

x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 \((-1)^{i+1} * sum[i] * (x - i + 1)\) 之和。

你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。

请你返回可以得到的 最大能量值 。

注意，选出来的所有子数组 不 需要覆盖整个数组。

示例 1：

输入：nums = [1,2,3,-1,2], k = 3
输出：22
解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。

示例 2：

输入：nums = [12,-2,-2,-2,-2], k = 5
输出：64
解释：唯一一种选 5 个不相交子数组的方案是：nums[0..0] ，nums[1..1] ，nums[2..2] ，nums[3..3] 和 nums[4..4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。

示例 3：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：选择 1 个子数组的最优方案是：nums[0..0] 。能量值为 -1 。

提示：

• 1 <= n <= 10^4
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= n
• 1 <= n * k <= 10^6
• k 是奇数。

Solution

我们看到这个数据范围，就知道肯定要再优化。
老样子，看到这样的式子，我们肯定考虑拆成2个组与1个组的简便形式，然后做一点变形。
写出转移方程：

\[dp[i][j]=max\{dp[i-1][v]+(pre[j]-pre[v-1])*(x-i+1)\} \ if \ i\%2==1 \]

\[dp[i][j]=max\{dp[i-1][v]-(pre[j]-pre[v-1])*(x-i+1)\} \ if \ i\%2==0 \]

那么，只需要维护与\(v\)相关的前缀最大值就可以了

class Solution {
public:long long maximumStrength(vector<int>& nums, int k) {int n=nums.size();const long long INF=1e18;vector<long long>pre(n+5,0);vector<vector<long long>>dp(k+5,vector<long long>(n+5,-INF));for(int i=1;i<=n;i++) pre[i]=pre[i-1]+nums[i-1];for(int i=0;i<=n;i++) dp[0][i]=0;for(int i=1;i<=k;i++){long long temp=-INF;for(int j=i;j<=n-(k-i);j++){dp[i][j]=max(dp[i][j],dp[i][j-1]);if(i%2){temp=max(temp,dp[i-1][j-1]-(k-i+1)*pre[j-1]);dp[i][j]=max(temp+pre[j]*(k-i+1),dp[i][j]);}else{temp=max(temp,dp[i-1][j-1]+(k-i+1)*pre[j-1]);dp[i][j]=max(temp-pre[j]*(k-i+1),dp[i][j]);}}}return dp[k][n];}
};

差几道题后面慢慢更，暂时做不出来，算法知识不允许