【递推型 dp】B006

一、Problem

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 输出：3 解释： 我们选中 [0,2], [8,10], [1,9] 这三个片段。 然后，按下面的方案重制比赛片段： 将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。 现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。

提示：

1 <= clips.length <= 100 0 <= clips[i][0] <= clips[i][1] <= 100 0 <= T <= 100

二、Solution

方法一：dp

定义状态： $f[i]$ 表示将前 $i$ 个时间点覆盖完需要的片段数 思考初始化： $f[i]=0，f[1...T]=INF$ 思考状态转移方程： 如果第 $j$ 个片段覆盖到视频点 $i$，则有 $f[i]=min(f[i],f[cs[j][0]]+1)$ 思考输出：$f[T]$

这里之是递推，是长度为 $i$ 视频片段的形成要依赖已拼接好的长度为 $i-1$ 的视频片段

class Solution { public int videoStitching(int[][] cs, int T) { int n = cs.length, INF = 0x3f3f3f3f, f[] = new int[T+1]; Arrays.fill(f, INF); f[0] = 0; for (int i = 0; i <= T; i++) for (int j = 0; j < n; j++) { if (cs[j][0] <= i && cs[j][1] >= i) f[i] = Math.min(f[i], f[cs[j][0]] + 1); } return f[T] == INF ? -1 : f[T]; } }

复杂度分析

时间复杂度：$O(T\times n)$，空间复杂度：$O(T)$，

---

方法二：贪心

思路

对于某一个视频片段 cs[i]，我们最好的决策就是找一个能与 cs[i] 有交集，且结束时间尽量靠后的一个 cs[idx]，然后再以该片段的结束时间 cs[idx][1] 为起点再做类似的查找

查找过程中，我们可能遇到的最优的还是上一次找到的片段，因此当再用 $O(n)$ 时间也找不到一个更优的片段时，应立即返回 -1

class Solution { public int videoStitching(int[][] cs, int T) { int n = cs.length, e = 0, cnt = 0; while (e < T) { int maxE = e; for (int i = 0; i < n; i++) { if (cs[i][0] <= e && cs[i][1] > maxE) maxE = cs[i][1]; } if (maxE == e) return -1; e = maxE; cnt++; } return cnt; } }

复杂度分析

时间复杂度：$O(n\times k)$，k 为未知数空间复杂度：$O(1)$，