划分型 DP
2024年3月17日大约 3 分钟
划分型 DP
判定能否划分
一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分。
枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 是否满足要求。
- 2369.检查数组是否存在有效划分 1780
- 139.单词拆分
最优划分
计算最少（最多）可以划分出多少段、最优划分得分等。
一般定义 f[i] 表示长为 i 的前缀 a[:i] 在题目约束下，分割出的最少（最多）子数组个数（或者定义成分割方案数）。
枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 对最优解的影响。
- 132.分割回文串 II
- 2707.字符串中的额外字符 1736
- 3196.最大化子数组的总成本 1847 也有状态机 DP 做法
- 2767.将字符串分割为最少的美丽子字符串 1865
- 91.解码方法
- 639.解码方法 II
- LCR 165.解密数字
- 1043.分隔数组以得到最大和 1916
- 1416.恢复数组 1920
- 2472.不重叠回文子字符串的最大数目 2013
- 1105.填充书架 2014
- 2547.拆分数组的最小代价 2020
- 2430.对字母串可执行的最大删除数 2102
- 2463.最小移动总距离 2454
- 2977.转换字符串的最小成本 II 2696
- 3441.变成好标题的最少代价 2765
- 2052.将句子分隔成行的最低成本（会员题）
- 2464.有效分割中的最少子数组数目（会员题）
约束划分个数
将数组分成（恰好/至多）k 个连续子数组，计算与这些子数组有关的最优值。
一般定义 f[i][j] 表示将长为 j 的前缀 a[:j] 分成 i 个连续子数组所得到的最优解。
枚举最后一个子数组的左端点 L，从 f[i−1][L] 转移到 f[i][j]，并考虑 a[L:j] 对最优解的影响。
注：对于恰好型划分 DP，可以通过控制内层循环的上下界，把时间复杂度从 O(nk) 优化至 O((n−k)k)。例如 3473 题。
- 813.最大平均值和的分组 1937
- 410.分割数组的最大值
- 1278.分割回文串 III 1979
- 1745.分割回文串 IV
- 1335.工作计划的最低难度 2035
- 1473.粉刷房子 III 2056
- 2209.用地毯覆盖后的最少白色砖块 2106
- 1478.安排邮筒 2190
- 3473.长度至少为 M 的 K 个子数组之和 2274 优化
- 1959.K 次调整数组大小浪费的最小总空间 2310
- 2478.完美分割的方案数 2344
- 3077.K 个不相交子数组的最大能量值 2557 优化
- 2911.得到 K 个半回文串的最少修改次数 2608
- 2912.划分数组得到最小的值之和 2735
不相交区间
- 2830.销售利润最大化 1851
- 2008.出租车的最大盈利 1872
- 2054.两个最好的不重叠活动 1883
- 1235.规划兼职工作 2023 做法不止一种
- 1751.最多可以参加的会议数目 II 2041
- 3414.不重叠区间的最大得分 2723
| 题目 | 难度 | |
|---|---|---|
| 2478. 完美分割的方案数 | 困难 | 方案数 |
| 3077. K 个不相交子数组的最大能量值 | 困难 | 不 需要覆盖整个数组 |
模板
3077. K 个不相交子数组的最大能量值
public class Solution3077 {
public long maximumStrength(int[] nums, int k) {
int n = nums.length;
long[] ps = new long[n + 1];
for (int i = 0; i < n; i++) {
ps[i + 1] = ps[i] + nums[i];
}
long[][] f = new long[k + 1][n + 1];
for (int i = 1; i <= k; i++) {
long w = (i % 2 > 0 ? 1 : -1) * (k - i + 1);
long mx = Long.MIN_VALUE;
f[i][i - 1] = mx;
for (int j = i; j < n - k + i + 1; j++) {
// for (int L = i - 1; L <= j - 1; L++) {
// mx = Math.max(mx, f[i - 1][L] + (ps[j] - ps[L]) * w);
// }
mx = Math.max(mx, f[i - 1][j - 1] - ps[j - 1] * w);
f[i][j] = Math.max(f[i][j - 1], ps[j] * w + mx);
}
}
return f[k][n];
}
}（全文完）