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