剪视频剪出一个贪心算法 | labuladong 的算法小抄

[giscus[bot]]

剪视频剪出一个贪心算法 | labuladong 的算法小抄

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 即将涨价！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 1024. Video St...

https://labuladong.github.io/algo/di-er-zhan-a01c6/tan-xin-le-9bedf/jian-shi-p-4302c/

[blueaken]

Integer[][] mem;
public int videoStitching(int[][] clips, int time) {
int n = clips.length;
mem = new Integer[time+1][n+1];

    // sort by start time 
    Arrays.sort(clips, (a, b) -> a[0] - b[0]);
    return dp(clips, time, n);
}

// dp function - return the min number of clips when clips array length is "size" and total during is "time"
int dp(int[][] clips, int time, int size) {

    // base case 1
    if (time == 0) {
        // when time is 0, answer is always 0
        mem[time][size] = 0;
        return mem[time][size];
    }

    // base case 2
    if (size == 0) {
        // when clip size is 0, there is always no answer, return -1
        mem[time][size] = -1;
        return mem[time][size];
    }

    if (mem[time][size] != null) {
        return mem[time][size];
    }

    int not_take_current = dp(clips, time, size-1);

    int take_current = -1;
    int[] cur = clips[size-1];
    if (cur[0] < time && cur[1] >= time) {
        take_current = dp(clips, cur[0], size-1);
    }

    // analyze results
    int res = -1;
    if (not_take_current == -1 && take_current != -1) {
        res = take_current + 1;
    } else if (not_take_current != -1 && take_current == -1) {
        res = not_take_current;
    } else if (not_take_current != -1 && take_current != -1) {
        res = Math.min(not_take_current, take_current + 1);
    }
    mem[time][size] = res;
    return res;
}