See this equivalent 2020-996 = 1024
said that if there is no 996 this year, you can live a good life (HHH
On 1024, the day of the programmer’s Day, basically knocked on the code of the day, but today I feel that my thinking has been blocked. There is no kind of active thinking thinking when I was in the past. The way to knock down will re -clarify the thinking, and will slowly make up the questions. I believe
Today’s force buckle is useful for dynamic planning. As soon as I encounter, I have practicing how to think:
teleportation door
At the beginning to look at the problem, I was a bit embarrassed. Later, I thought about it. Now I try to express my thoughts:
First of all, one array stores some video fragments. These video clips are composed of [Starting Time, End Time]
To find a clip that can be edited into 0 to T, because there are many fragments, there may be many editing methods to achieve the purpose. Find the least video clips to edit
The idea of taking the Taoism is to edit it into a video with 0 to T, which means that the fragment used to edit should cover the entire 0 to T, so that it is possible to edit. This method is judged whether it can be successful. After thinking about it, it should be O (t*clips.size ())
It took me a long time to judge for so long.

After
, my idea is to contribute. One fragment has come to the range of 0 to T. It is better than fewer than less. This should be greedy, but the technical reason doesn’t know how to achieve it
After I can’t knock out to see the problem solving … I went back to think about it when I saw the dynamic plan.
dp [i] to indicate the minimum fragment required to edit to 0 to i
First of all, when I == 0, the empty fragment can be cut out. In other words, the empty set is the subset of any set,
When traversing to the fragment, if I have cut the video from 0 to the beginning of the clip, then I can edit the video at the end of 0 to the end of the fragment, that is, after connecting this segment to In this total clip, that means the minimum number of fragments to be used to cut into 0 to the beginning of the clip with DP [fragment], plus the current segment can be completed.
, that is, the state transfer is like this:
dp [i] = The minimum value of the DP value +1 starting at each clip
Still the official explanation is better HHH
We can enumerate all the sub -interval to calculate all the DP values in turn. We first enumerate i, and at the same time, for any sub -interval [AJ, BJ), if it meets AJ <i ≤ BJ, then it can cover the second half of the interval [0, i), and the first half can be used in DP. [AI] The optimal method corresponding to +1 is covered, so we can use DP [AJ] +1 to update DP [i]
The final answer is DP [T]

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];
    }
};