1024Video Stitching视频拼接

  • 时间:
  • 来源:互联网
  • 文章标签:

题目描述

今天是程序员节,祝各位节日快乐!码到成功!

这是属于程序员的最好的时代!现在不努力,更待何时?

好,下面来看题解(C++)。

这道题采用了动态规划的解法。

dp[i]代表覆盖0-i所需片段的最小数目。

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        vector<int> dp(T+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=T;i++){
            for(auto& it:clips){
                if(it[0]<i&&i<=it[1]){
                    dp[i]=min(dp[i],dp[it[0]]+1);
                }
            }
        }
        return dp[T]==INT_MAX-1?-1:dp[T];
    }
};

本文链接http://www.taodudu.cc/news/show-1782086.html