动态规划是运筹学中用于求解决策过程中的最优化数学方法。一种使用多阶段决策过程最优的通用方法。

如果问题是由交叠的子问题所构成,我们就可以用动态规划技术来解决它,一般来说,这样的子问题出现在对给定问题求解的递推关系中,这个递推关系包含了相同问题的更小子问题的解。动态规划法建议,与其对交叠子问题一次又一次的求解,不如把每个较小子问题只求解一次并把结果记录在表中(动态规划也是空间换时间的),这样就可以从表中得到原始问题的解。

动态规划的思想是什么:记忆,空间换时间,不重复求解,由交叠子问题从较小问题解逐步决策,构造较大问题的解。

计算二项式系数

C(n, k) = C(n-1, k-1) + C(n-1, k)

如果元素存在于这n个数选出的k个数中间,那么就将其计数在剩余n-1个元素的k-1大小的子集里C(n-1, k-1),如果元素不在其中,那么就检查k大小的子集C(n-1, k),所以C(n, k) = C(n-1, k-1) + C(n-1, k)

这个式子将C(n , k)的计算问题表述为了(问题描述)C(n-1 , k-1)和C(n-1, k)两个较小的交叠子问题。

初始条件:C(n , n) = C(n , 0) = 1C(0, k) = 0, k>0

一个递归版本

1
2
3
4
5
@memo
def C(n, k):
if k == 0: return 1
if n == 0: return 0
return C(n-1, k-1) + C(n-1, k)

迭代版的,辅助数据结构是一个二维列表或者一个以坐标为键的字典。但是填充的基本是下三角矩阵,因为不可能有C(1,3)这种出现,最多是对角线上的C(3,3)

1
2
3
4
5
6
7
8
9
10
11
12
13
def iter_C(n, k):
from collections import defaultdict
C = defaultdict(int)
# 遍历所有行,n中每一个元素代表一行
# 控制行,填到n行
for row in range(n+1):
# 第二个for控制每行到哪,最大不超过n,n和k的最小值
for col in range(min(n+1,k+1)):
if col == row or col == 0 or row == 0:
C[row, col] = 1
continue
C[row, col] = C[row-1, col-1] + C[row-1, col]
return C[n, k]

可以看出来这个算法复杂度是n*k

动态规划的几个要点:

  • 怎么描述问题,要把问题描述为交叠的子问题
  • 交叠子问题的初始条件(边界条件)
  • 动态规划在形式上往往表现为填矩阵的形式,有的可以优化空间复杂度,开一个数组即可,优化也是根据递推式的依赖形式的,
  • 填矩阵的方式(或者说顺序)表明了什么?–它表明了这个动态规划从小到大产生的过程,专业点的说就是递推式的依赖形式决定了填矩阵的顺序。

一是填矩阵的顺序,二是动态规划空间复杂度的优化:这2点都跟递推式的依赖关系有关(这是本质),在形式上就表现为填矩阵的时候你的顺序要确保每填一个新位置时你所用到的那些位置(即它依赖的)要已经填好了,在空间优化上表现为当一个位置在以后还有用的时候你不能覆盖它。

象棋问题

国际象棋中的车可以水平的或竖直的移动,一个车要从一个棋盘的一角移到对角线的另一角,有多少种最短路径?

  • 用动态规划算法求解
  • 用初等排列组合知识求解

对于第二种,很简单,棋盘大小是n,那么从(0,0)到(n,n)不论怎样要走2n步,而且横走n,竖走n,所以应该是有C(2n, n)种

动态规划,主要是建立递推式

C[i , j]表示从(0,0)移动到(i ,j)的方法数。那么主要是怎么刻画C[i, j]的含义,这是动态规划的一个关键点。

那么要走到C[i, j]那么上一步必定是C[i-1,j]或者C[i,j-1],分析动态规划问题的逆向思维,这样就把问题描述成了交叠子问题

C[i , j] = C[i -1, j] + C[i , j-1]

初始条件:

C[0, j] = 1, j从0到nC[i, 0] = 1, i从0到n

实现:

1
2
3
def chess(i, j):
if i == 0 or j == 0: return 1
return chess(i-1, j) + chess(i, j-1)

但是如果只是这样,计算chess(100, 100)就很慢了,所以加上记忆体化。

1
2
3
4
5
6
7
8
9
10
11
12
13
from functools import wraps
def memo(func):
cache = {}
@wraps(func)
def wrapper(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrapper
@memo
def chess(i, j):
if i == 0 or j == 0: return 1
return chess(i-1, j) + chess(i, j-1)

迭代版:

1
2
3
4
5
6
7
8
9
10
def iter_chess(i, j):
from collections import defaultdict
chess = defaultdict(int)
for row in range(i+1):
for col in range(j+1):
if row == 0 or col == 0:
chess[row, col] = 1
continue
chess[row, col] = chess[row-1, col] + chess[row, col-1]
return chess[i, j]

最大子数组之和

一个经典的动态规划问题:最大子数组之和。其原理就是将求全局最优解变成了求解局部最优解,然后推得全局最优解。本身是一种最优化算法。这里就是将整个数组的最大子数组之和变成了局部小数组的最大子数组之和,然后递推到全部数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = {}
dp[0] = nums[0]
res = dp[0]
for i in range(1, len(nums)):
if dp[i-1] > 0:
dp[i] = nums[i] + dp[i-1]
else:
dp[i] = nums[i]
res = max(dp[i], res)
return res

规划Programming是指完成一组选择,线性规划。动态是指会随时间发生变化,其所做的每一个选择都必须依赖于前一个选择。具体到算法设计的运用中,DP技术的核心其实就是一种高速缓存caching。问题分解依然是递归和归纳。DP算法通常是通过反转相应的递归函数,使其对某些数据结构进行逐步迭代和填充,如多维数组。在Python中,一般在实现相关递归函数时候直接从缓存中返回值。如果可以用同一个参数执行多次调用,其返回结果就会直接来自于缓存,这种方式是记忆体化。

对于一个斐波那契函数:

1
2
3
def fib(i):
if i < 2: return 1
truetruereturn fib(i-1) + fib(i-2)

记忆体化的装饰器函数:

1
2
3
4
5
6
7
8
9
from functools import wraps
def memo(func):
cache = {}
truetrue@wraps(func)
truetruedef wrap(*args):
truetrue if args not in cache:
truetruetruetrue cache[args] = func(*args)
truetruetruetruereturn cache[args]
truetruereturn wrap

这样fib = meme(fib),在使用fib(100)的时候,就不会崩掉了。这个内存化函数的思路就是缓存其自身的返回值。就是如果将同一参数再次调用的话,就可以返回缓存中的值。可以将其作为函数中的一种缓存逻辑,memo函数是一个可重用更好的解决方案。

斐波那契函数有两个子问题,并且两个子问题中存在复杂依赖,所以面对的事一组相互重叠的子问题。

求2的指数的递归式:

1
2
3
def two_pow(i):
if i == 0: return 1
truetruereturn two_pow(i-1) + two_pow(i-1)

如果引入memo函数,那么就很高效了,因为缓存会给第二次或者以上的调用直接返回值。这样就把递归调用的数量从2降到了1,从而将指数级的运行时间降为了线性级。666。当各级子问题之间存在重叠的时候,其带来的冗余运算就会变成指数级操作。如下图

那么最开始的那个迭代版的最大子数组和的问题,转换成递归版就是这样:但是将这个代码在leetcode提交,爆栈~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def dp_solution(i, max_num):
if i == 0:
return nums[0], nums[0]
dp_deep, max_num = dp_solution(i-1, max_num)
if dp_deep > 0:
res = dp_deep + nums[i]
else:
res = nums[i]
max_num = max(max_num, res)
return res, max_num
return dp_solution(len(nums) - 1, 0)[1]

使用了记忆体来缓存,然后再用迭代的方式来逐个求值,这样就解决了上述问题,因为即使在做最大长度的时候,之前的值都已经缓存了,所以栈的深度就保持在1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
from functools import wraps
def memo(func):
cache = {}
@wraps(func)
def wrapper(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrapper
@memo
def dp_solution(i):
if i == 0:
return nums[0]
dp_deep = dp_solution(i-1)
if dp_deep > 0:
res = dp_deep + nums[i]
else:
res = nums[i]
return res
return max(dp_solution(i) for i in range(len(nums)))

拓扑排序

拓扑排序,对一个有向无环图,寻找其中依赖顺序的过程,寻找所有沿着特定顺序前进的边和点。基于DAG的算法,寻找DAG的最短路径,以及大多数的基于动态规划的算法,都是先进行拓扑排序作为初始化步骤的,至于为什么,仔细悟一下就知道了,子问题的求解嘛,要按顺序来。

一个简单递归版的拓扑排序

1
2
3
4
5
6
7
8
9
10
def naive_topsort(G, S=None):
if S is None: S = set(G)
truetrueif len(s) == 1: return list(S)
truetruev = S.pop()
truetrueseq = naive_topsort(G, S)
truetruemin_i = 0
truetruefor i, u in enumerate(seq):
truetrue if v in G[u]: min_i = i + 1
truetrueseq.insert(min_i, v)
truetruereturn seq

程序的关键在于每次移除一个节点,然后解决其余n-1个节点的问题。然后再结束迭代的时候,根据是否被索引确定在排序结果中的位置。当然如果是同级的话,后面的插入的顺序在之前插入的前面。

但是更加优化的算法应该是找出放在首端的元素,然后从图中移除,这样图仍然是一个DAG,所以是一个等效的,规模缩小的问题。要找的是一个没有入边的节点。

首先用计数的方式来查找没有入边的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def topsort(G):
count = dict((u, 0) for u in G)
truetruefor u in G:
truetrue for v in G[u]:
truetruetruetrue count[v] += 1
truetrue# 首端元素
truetrueQ = [u for u in G if count[u] == 0]
truetrueS = []
truetruewhile Q:
truetrue u = Q.pop()
truetruetruetrueS.append(u)
truetruetruetruefor v in G[u]:
truetruetruetrue count[v] -= 1
truetruetruetruetruetrueif count[v] == 0:
truetruetruetruetruetrue Q.append(v)
truetruereturn S

有向无环图中的最短路径问题

动态规划的核心是决策顺序的问题,每一次决策都会导致新的局面,所以需要根据期望的局面来找出最好的选择顺序。贪心算法类似,只是它是基于当下做出最好的选择,并没有考虑全局。

有向无环图的最短路径问题就是一个决策顺序的问题,将决策过程中的每一个可能的决策状态视为一个独立的节点,出边表示了在各种状态下所做出的可能选择。

设v到终点的距离是d(v),边(u,v)的权值是w(u, v),如果位于节点u,那么就知道了其邻接节点v的d(v),所以最小表达式是w(u, v) + d(v)

一个解决DAG的最短路径问题的代码:

1
2
3
4
5
6
7
def rec_dag_sp(W, s, t):
@memo
truetruedef d(u):
truetrue if u == t: return 0
truetruetruetrue# 对于所有可能的u出度的节点,求最小值
truetruetruetruereturn min(W[u][v] + d[v] for v in W[u])
truetruereturn d(s)

对于DP算法,将其转换成迭代形式会更好。迭代版采用了松弛法,通过逐步扩展局部方案来解决问题,可以被用来反转归纳法的设计。即考虑是如何到达节点v的,所以就得扩展来自v之前的所有节点的答案。就是将入边松弛化。

松弛化的方法就是拓扑排序。在递归版本中并没有单独进行一次拓扑排序,因为其隐式的进行了一次DFS遍历,并且按照遍历顺序来进行所有的更新。但是对于迭代方式来说,需要一次独立的拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
def dag_sp(W, s, t):
truetrue# 将所有边都最大化,然后再松弛
d = {u: float('inf') for u in W}
truetrued[s] = 0
truetruefor u in topsort(W):
truetruetruetrue# 从s开始,d[u] = d[s] = 0
truetrue if u == t: break
truetruetruetruefor v in W[u]:
truetruetruetruetruetrue# 找到 u到v的最小值,其实也是一种递归方法
truetruetruetruetruetrue# 从u的最小距离推v的最小距离
truetruetruetrue d[v] = min(d[v], d[u] + W[u][v])
truetruereturn d[t]

原理就是找到拓扑排序,就找到了一种顺序先后位置。这样从起点开始,松弛出边,按照拓扑排序循环下去,找到 从起点到该节点的最小距离。

尽量松弛化出自之前所有可能的节点的边,拓扑排序靠前的。所以必须给当前节点的入边进行松弛化。

记忆体化的递归方式,带松弛法的迭代方式。递归方式,从起点开始,尝试各种下一步的操作,然后对其余部分进行递归处理。迭代版本的话,可以按照拓扑排序对各个节点的出边进行松弛化,也可以松弛化每个节点的入边。

最长递增子序列问题

大多数DP问题中,可能没有一个明确的关系图,必须发掘出响应的DAG或者决策序列进程。DP问题首先要对子问题进行定义。需要了解所有需要知道的预置行为(也就是说子问题的可能)以及归纳步骤,这是弄清楚其他元素的前提条件。意味着需要找到每一种预置条件下的最长递增子序列。所以以各个指定的位置为重点,找序列的最长递增子序列。如果知道了前k位子序列的方法,也就知道了k+1位的子序列。但是用直接递归来实现会带来指数运行的时间,所以需要使用缓存,去掉指数级的冗余部分。

1
2
3
4
5
6
7
8
9
def rec_lis(seq):
@memo
truetruedef L(cur):
truetrue res = 1
truetruetruetruefor pre in range(cur):
truetruetruetrue if seq[pre] <= seq[cur]:
truetruetruetruetruetrue res = max(res, 1 + L(pre))
truetruetruetruereturn res
truetruereturn max(L(i) for i in range(len(seq)))

迭代版需要将递归调用切换成一个查找过程,然后封装成循环。

1
2
3
4
5
6
7
def basic_lis(seq):
L = [1] * len(seq)
truetruefor cur, val in enumerate(seq):
truetrue for pre in range(cur):
truetruetruetrue if seq[pre] <= val:
truetruetruetruetruetrue L[cur] = max(L[cur], 1+L[pre])
truetruereturn max(L)

DAG的思路,序列中的每个元素都被视为图中一个节点,并且每个节点到比它大的节点之间都会存在一条隐藏的边,都会存在一个递增子序列。现在就是DAG的最长路径问题。其实在判断每个前面的元素是不是一个有效的节点,如果是,则会当成入边进行松弛化处理,遍历完所有的前面节点,取最大值。前置步骤就是当前节点的入边或者有效前辈节点,也就是说在得到这个节点的结果所需要的条件。

DP问题有时会使用递归分解和归纳法,有时会用DAG结构来构建问题。当然这个算法是一个n2的算法。算法时间主要集中在查找上,从当前位置之前的元素找出最符合条件的前辈节点集。可以将线性搜索转换成二分搜索。

对于一个长度为m的子序列,终点有多个前辈节点,那么应该选用值比较小的那一个前辈节点,因为这样不会漏掉后面介于小和大之前的元素。

1
2
3
4
5
6
7
8
9
from bisect import bisect
def lis(seq):
end = []
truetruefor val in seq:
truetrue idx = bisect(end, val)
truetruetruetrue# 找到大的,插入
truetruetruetrueif idx == len(end): end.append(val)
truetruetruetrueelse: end[idx] = val # 小的只改变值,但是长度不变
truetruereturn len(end)

DP方式解决问题的时候,递归分解和归纳思想,需要证明一个问题的整体的最佳方案或者正确方案取决于子问题的最佳方案或正确方案。DP和分治法的区别在于DP允许子问题之间彼此重叠。其实就是寻找带有重叠的分解操作,只要消除重叠部分,就是一个有效的方案。

序列比对问题

两个序列之间的最长公用子序列(LCS),编辑距离是将一个序列更改成另一个序列所需的编辑操作数。如果长度为m,n的两个序列之间的最长公用子序列的长度为k,那么不允许替换操作下,之间的编辑距离应为m+n-2k。

关键是要设计出一个能够反映彼此关联的子问题的集合,是一种带有复杂依赖的递归分解。这些子问题设计为索引之类的参数可以称为归纳变量。

可以将a和b的LCS长度表示一个关于i,j的函数,i,j就是两个序列的长度。

1
2
3
4
5
6
7
def rec_lcs(a, b):
@memo
truetruedef L(i, j):
truetrue if min(i, j) < 0: return 0
truetruetruetrueif a[i] == b[j]: return 1 + L(i-1, j-1)
truetruetruetruereturn max(L(i-1, j), L(i, j-1))
truetruereturn L(len(a) - 1, len(b) - 1)

可以简单的将其看作一个动态决策过程,是拿掉第一个序列的元素,还是第二个的,还是两边都拿掉。

反转成下面的迭代版本:

1
2
3
4
5
6
7
8
9
10
11
def lcs(a, b):
n, m = len(a), len(b)
pre, cur = [0] * (n + 1), [0] * (n+1)
truetruefor j in range(1, m+1):
truetrue pre, cur = cur, pre
truetruetruetruefor i in range(i, n+1):
truetruetruetrue if a[i-1] == b[j-1]:
truetruetruetruetruetrue cur[i] = pre[i-1] + 1
truetruetruetruetruetrueelse:
truetruetruetruetruetrue cur[i] = max(pre[i], cur[i-1])
truetruereturn cur[n]

pre[i-1]L(i-1, j-1)cur[i-1]L(i-1, j)pre[i]表示L(i, j-1),反正我是想不出来这个算法的。。。

背包问题

一组物品,有各自的质量和价值,背包有一定的容量,放入背包的东西应该总质量小于或者等于背包容量,总价值最大。

这种问题应该作为一种模式来思考,就是需要以某种形式来定义问题的子问题,递归这些子问题之间的关系,确保每个子问题都只被计算一次,隐式或者显式的记忆体化处理。

使用背包容量归纳推导来参数化问题,如果设背包剩余容量r所能达到的最大价值为m(r),r中的每一个值都表示一个子问题。递归分解过程就围绕这背包容量中最后一个单元是否有用来进行,没用m(r) = m(r-1),有用则选取合适对象。m(r) = v[i] + m(r-w[i]),嗯,很有道理。

1
2
3
4
5
6
7
8
9
10
11
12
def rec_unbounded_knapsack(w, v, c):
@memo
truetruedef m(r):
truetrue if r == 0: return 0
truetruetruetrue# 递归到最后一层,然后找最大价值符合质量的
truetruetruetrueval = m(r-1)
truetruetruetruefor i, wi in enumerate(w):
truetruetruetrue if wi > r: continue
truetruetruetruetruetrue# 当前节点以及剩余质量所满足的节点
truetruetruetruetruetrueval = max(val, v[i] + m(r-wi))
truetruetruetruereturn val
truetruereturn m(c)

下面是迭代版本

1
2
3
4
5
6
7
8
9
10
def unbounded_knapsack(w, v, c):
# 使用列表作为缓存
m = [0]
truefor r in range(1, c+1):
true val = m[r-1]
truetruefor i, wi in enumerate(w):
truetrue if wi > r: continue
truetruetrueval = max(val, v[i] + m[r-wi])
truetruem.append(val)
truereturn m[c]

0-1背包问题

每个对象最多只能用一次。

思路如下:设前k个对象的最大价值为m(k,r),r为剩余背包容量,如果k=0或者r=0,那么m(k,r)=0,其他情况,就是一种决策了。只需要考虑是否要纳入最后一个对象,如果否,那么m(k,r) = m(k-1, r),而且如果w[i]>r,就只能删除这个对象。

如果是,m(k,r) = v[i] + m(k-1, r-w[i]),然后选择值最大的那个

1
2
3
4
5
6
7
8
9
def rec_knapsack(w, v, c):
@memo
truedef m(k, r):
true if k == 0 or r == 0: return 0
truetruei = k - 1
truetruedrop = m(k-1, r)
truetrueif w[i] > r: return drop
truetruereturn max(drop, v[i] + m(k-1, r-w[i]))
truereturn m(len(w), c)

这样看来的确很简单,看来分析是比较重要的。迭代版:

1
2
3
4
5
6
7
8
9
10
11
12
13
def knapsack(w, v, c):
n = len(w)
truem = [[0] * (c+1) for i in range(n+1)]
trueP = [[False]*(c+1) for i in range(n+1)]
truefor k in range(1, n+1): #使用的前k个东西
true i = k -1
truetruefor r in range(1, c+1): # 每一个可能的容量
truetrue m[k][r] = drop = m[k-1][r] # 扔掉
truetruetrueif w[i] > r: continue
truetruetruekeep = v[i] + m[k-1][r-w[i]]
truetruetruem[k][r] = max(drop, keep)
truetruetrueP[k][r] = keep > drop
truereturn m, P

序列的二元分割

用某种方式来递归分割某些序列

  • 矩阵连乘
  • 解析与上下文无关的语言
  • 最优搜索树

问题的本质是按层次将序列分成区块,使其中每一区块都包含另外两个区块,同时找到产生最佳性能或者最佳值的划分方式。

如果想要创建一颗按序排列的平衡二叉搜索树,需要选择中间值作为分割点,也就是根节点,然后递归创建左平衡子树和右平衡子树。这就是leetcode里面刷过的一道题。

这里要从多个分割点中选择一个最合理的分割点,要试遍每一个可能的分割点,就是一个DP问题,在有向无环图中找到最短路径。最短路径问题可以概括为DP中的序列选择。序列分解问题可归类于包含重叠部分的递归分解。

困了,明日再研究~。。。