【leetcode】1024. 视频拼接（video-stitching）（DP）[中等]

链接

https://leetcode-cn.com/problems/video-stitching/

耗时

解题：1 h
题解：16 min

题意

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

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

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

思路

dp[i][j] 表示运动过程 i 开始，j 结束，时长 [i, j] 所需片段的最小数目。

初始化，将所有能直接剪辑得到的视频片段的 dp[i][j] 都置为 1，i==j 都置为 0，其它全部 INF。

除了 dp[i][j]==1，剩下的每个片段 [i, j]，都用可能的 k (i<k<j) 分割，尝试找到最小的划分。

状态转移方程：

d p [ i ] [ j ] = { min ⁡ k = i + 1 j − 1 d p [ i ] [ k ] + d p [ k ] [ j ]        i < j I N F                                            其 它 dp[i][j] = \begin{cases} \min_{k=i+1}^{j-1} dp[i][k]+dp[k][j] \ \ \ \ \ \ i<j \\ INF \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 其它 \end{cases} dp[i][j]={mink=i+1j−1​dp[i][k]+dp[k][j]      i<jINF                                          其它​

时间复杂度： O ( T 3 ) O(T^3) O(T3)

AC代码

class Solution {
private:
    static constexpr int INF = 0x3f3f3f3f;
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        vector<vector<int>> dp(T+1, vector<int>(T+1, INF));
        
        // init
        for(int i = 0; i <= T; ++i) dp[i][i] = 0;
        for(auto clip : clips) {
            for(int i = clip[0]; i <= min(clip[1], T); ++i) {
                for(int j = i+1; j <= min(clip[1], T); ++j) {
                    dp[i][j] = 1;
                }
            }
        }
        
        // dp
        for(int i = T; i >= 0; --i) {
            for(int j = i+1; j <= T; ++j) {
                if(dp[i][j] == 1) continue;
                for(int k = i+1; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
                }
            }
        }
        
        return dp[0][T]==INF?-1:dp[0][T];
    }
};