【数据结构算法】动态规划

2021年01月09日

Author: Guofei

文章归类: 8-数据结构与算法，文章编号: 555

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2021/01/09/greedy.html

Edit

贪心算法

贪心算法本质上是动态规划的一种，它只着眼于当前阶段的最优解，所以每个子问题只被计算一次，期望得到的局部最优解是全局最优解。

TODO:思考可以使用贪心的充要条件

入门题目

分糖果问题

m个糖果，n个孩子（m小于n）
m个糖果大小是 s1,s2,…,sm
n个孩子对糖果的需求是 g1,g2,…,gn
要求分糖果，使满足的孩子最多

s = [1, 3, 5, 6, 3, 1]

n = [3, 4, 5, 3, 3, 3, 1, 2]

s.sort(reverse=True)
n.sort(reverse=True)
for idx_s, num_s in enumerate(s):
    for idx_n, num_n in enumerate(n):
        if num_s >= n[idx_s]:
            pass

res = 0
idx1, idx2 = 0, 0
while idx2 < len(n) and idx1 < len(s):
    if s[idx1] >= n[idx2]:
        idx1 += 1
        idx2 += 1
        res += 1
    else:
        idx2 += 1

res

⽆无重叠区间

https://leetcode.com/problems/non-overlapping-intervals/

给定数个区间，最少移除几个区间，使剩余区间不重叠？（接壤的区间认为不重叠）

这题的答案看起来非常简洁：先按照右区间递增排序，再从左到右遍历，去除重叠即可。

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

intervals = sorted(intervals, key=lambda x: x[1])

idx1, idx2 = 0, 1
res = 0
len_intervals = len(intervals)
while idx1 < len_intervals and idx2 < len_intervals:
    if intervals[idx1][1] <= intervals[idx2][0]:
        idx1, idx2 = idx2, idx2 + 1
    else:
        idx2 += 1
        res += 1

res

但是这个题的思考过程是很复杂的。

方案1:组合穷举。
我们把所有的可能组合列出来，然后剔除不满足条件的组合。显然就是个 DFS/BFS 问题，可以用递归或遍历法。幂级复杂度。

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
res = [[]]
for i in intervals:
    res = [j + res_ for res_ in res for j in [[i], list()]]
res

上面的代码把所有幂级别的情况列出来，在此基础上判断是否重合，然后看看哪个最长。

方案2:组合穷举的基础上剪枝。
DFS/BFS 解法，如何涉及到高复杂度，必然意味着存在剪枝的做法。
先按照左区间升序排序，显然，仅需要判断前一个节点与待加入的节点是否重叠，就可以判断是否剪掉。

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
intervals = sorted(intervals, key=lambda x: x[0])


def is_correct(res_, j):
    if j:
        if res_:
            if res_[-1][1] > j[0][0]:
                return False
    return True


res = [[]]
for i in intervals:
    res = [res_ + j for res_ in res for j in [[i], list()] if is_correct(res_, j)]
res

得到的结果一定不重合，算一下哪个长即可。

方案3：继续剪枝
考虑到我们其实不需要输出最优组合，而是只需要返回一个数字（最长长度），因此可以进一步剪枝。

例如，如果某个组合的最右区间是3、最长长度是2；那么最右区间是3、最长长度是1的组合就没必要去计算了。

TODO: 这一块代码不太好写成遍历的形式，后面补上。

方案4：使用等价于方案3的递归法

根据方案3，自然想到问题可以抽象成一个映射：f(n) ，代表n左边的区间集，最长有多少个。

import numpy as np

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
intervals = []
intervals = sorted(intervals, key=lambda x: x[0])


def func(n):
    # 含有n个区间的集合，最后一个区间是哪一个，当前几个区间，总的右端点是什么
    if n == 0:
        return None, 0, None
    if n == 1:
        idx, selected_num, right_bound = None, 1, np.inf
        for idx_item, item in enumerate(intervals):
            if item[1] < right_bound:
                idx = idx_item
                right_bound = item[1]
        return idx, selected_num, right_bound

    else:
        idx, selected_num, left_bound = func(n - 1)
        if selected_num < n - 1:
            return idx, selected_num, left_bound
        right_bound = np.inf
        add_one = 0
        for idx_item, item in enumerate(intervals[idx + 1:], start=idx + 1):
            if item[0] >= left_bound:
                if item[1] < right_bound:
                    idx = idx_item
                    add_one = 1
                    right_bound = item[1]
        return idx, selected_num + add_one, right_bound


func(0)[1]

方案4：动态规划

贪心算法的充分条件

一致的单调趋势。例如，上面的问题，我们构造的函数f(n)，是任选n个区间，其右界最小是多少。显然这个函数是单调递增的。构造这个函数时，最先想到的是，从左到右迭代，选到第n个区间时，f(n) 是右界，这个函数就不单调。
- 一种常见的条件是，子问题不取决于父问题如何选择。
可迭代，否则父问题无法分解到子问题，就没什么意义。也就是说，给定f(n-1),f(n-2)等，可以计算出f(n)，未必有直接的数学公式，但用代码可以表达出来。上面的例子中，知道f(n-1)后，可以在待定区间内寻找更右边的区间，如果能慢猪，即可求出f(n)=f(n-1)+1

您的支持将鼓励我继续创作！

【数据结构算法】动态规划