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~~dp [i] to indicate the minimum fragment required to edit to 0 to i

, 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.

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