贪心与动态规划

贪心与动态规划的区别：

• 贪心的正确性需要证明（归纳法或反证法）

• 贪心没办法撤销选择，只能从局部向全局优化。动态规划可以撤销选择，因为记录了所有“曾经“的局部优化，从而可以选择不同方案来寻求最终解。

如果可以证明贪心的正确性，那么贪心的时间复杂度一般比动态规划要低。下面的例子都有O(n)的贪心和O(n²)的动态规划解法。

跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

O(n)贪心

def jump(nums):
    far, end, res = 0, 0, 0
    for i in range(len(nums)-1):
        far = max(far, i+nums[i])
        if i == end:
            end = far
            res += 1
    return res

O(n2)动态规划

def jump(nums):
    f = [float('inf') for _ in range(len(nums))]
    f[0] = 0
    for i in range(1, len(nums)):
        for j in range(i):
            if f[j]<float('inf') and nums[j]>=i-j:
                f[i] = min(f[i], f[j]+1)
    return f[-1]a

视频拼接

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

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

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

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出：3
解释：
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。

除了之前的排序要O(nlogn)，贪心算法主体是O(n)的时间复杂度。

O(n)贪心

def videoStitching(clips, T):
    if T==0: return 0
    clips.sort(key=lambda x: x[0]) # sorting is O(nlogn)
    i = get = res = 0
    while i < len(clips) and clips[i][0] <= get:
        far = get
        while i < len(clips) and clips[i][0] <= get:
            far = max(far, clips[i][1])
            i += 1
        get = far
        res += 1
        if get>=T: return res
    return -1

O(n2)动态规划

def videoStitching(clips, T):
    # f[i] = minimum clips needed for covering [0, i]
    # f[i] = f[i-1] + 1 if one clip covers [i, i]
    # f[0] = 0
    f = [float('inf') for _ in range(T+1)]
    f[0] = 0
    for i in range(1, len(f)):
        for aj, bj in clips:
            if aj < i <= bj:
                f[i] = min(f[i], f[aj] + 1)
    return f[-1] if f[-1] < float('inf') else -1