# Python Algorithms - C8 Dynamic Programming

## Hujiawei Bujidao

Python算法设计篇(8) Chapter 8 Tangled Dependencies and Memoization

—— Ambrose Bierce, The Devil’s Dictionary

[这篇文章实际写作时间在这个系列文章之前，所以写作风格可能略有不同，嘿嘿]

1.直接自顶向下实现递归式，并将中间结果保存，这叫备忘录法；

2.按照递归式自底向上地迭代，将结果保存在某个数据结构中求解。

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


from functools import wraps

def memo(func):
cache={}
@wraps(func)
def wrap(*args):
if args not in cache:
cache[args]=func(*args)
return cache[args]
return wrap

@memo
def fib(i):
if i<2: return 1
return fib(i-1)+fib(i-2)


def fib_iter(n):
if n<2: return 1
a,b=1,1
while n>=2:
c=a+b
a=b
b=c
n=n-1
return c


from functools import wraps

def memo(func):
cache={}
@wraps(func)
def wrap(*args):
if args not in cache:
cache[args]=func(*args)
return cache[args]
return wrap

@memo
def cnk(n,k):
if k==0: return 1 #the order of if should not change!!!
if n==0: return 0
return cnk(n-1,k)+cnk(n-1,k-1)


from collections import defaultdict

n,k=10,7
C=defaultdict(int)
for row in range(n+1):
C[row,0]=1
for col in range(1,k+1):
C[row,col]=C[row-1,col-1]+C[row-1,col]

print(C[n,k]) #120


1.“去哪里?“：我们顺向思维，首先假设从a点出发到所有其他点的距离都是无穷大，然后，按照拓扑排序的顺序，从a点出发，接着更新a点能够到达的其他的点的距离，那么就是b点和f点，b点的距离变成2，f点的距离变成9。因为这个有向无环图是经过了拓扑排序的，所以按照拓扑顺序访问一遍所有的点(到了目标点就可以停止了)就能够得到a点到所有已访问到的点的最短距离，也就是说，当到达哪个点的时候，我们就找到了从a点到该点的最短距离，拓扑排序保证了后面的点不会指向前面的点，所以访问到后面的点时不可能再更新它前面的点的最短距离！(这里的更新也就是前面第4节介绍过的relaxtion)这种思维方式的代码实现就是迭代版本。

[这里涉及到了拓扑排序，前面第5节Traversal中介绍过了，这里为了方便没看前面的童鞋理解，W直接使用的是经过拓扑排序之后的结果。]

def topsort(W):
return W

def dag_sp(W, s, t):
d = {u:float('inf') for u in W} #
d[s] = 0
for u in topsort(W):
if u == t: break
for v in W[u]:
d[v] = min(d[v], d[u] + W[u][v])
return d[t]

#邻接表
W={0:{1:2,5:9},1:{2:1,3:2,5:6},2:{3:7},3:{4:2,5:3},4:{5:4},5:{}}
s,t=0,5
print(dag_sp(W,s,t)) #7


2.“从哪里来?“：我们逆向思维，目标是要到f，那从a点经过哪个点到f点会近些呢?只能是求解从a点出发能够到达的那些点哪个距离f点更近，这里a点能够到达b点和f点，f点到f点距离是0，但是a到f点的距离是9，可能不是最近的路，所以还要看b点到f点有多近，看b点到f点有多近就是求解从b点出发能够到达的那些点哪个距离f点更近，所以又绕回来了，也就是递归下去，直到我们能够回答从a点经过哪个点到f点会更近。这种思维方式的代码实现就是递归版本。

from functools import wraps
def memo(func):
cache={}
@wraps(func)
def wrap(*args):
if args not in cache:
cache[args]=func(*args)
# print('cache {0} = {1}'.format(args[0],cache[args]))
return cache[args]
return wrap

def rec_dag_sp(W, s, t):
@memo
def d(u):
if u == t: return 0
return min(W[u][v]+d(v) for v in W[u])
return d(s)

#邻接表
W={0:{1:2,5:9},1:{2:1,3:2,5:6},2:{3:7},3:{4:2,5:3},4:{5:4},5:{}}
s,t=0,5
print(rec_dag_sp(W,s,t)) #7


[扩展内容：对DAG求单源最短路径的动态规划问题的总结，比较难理解，附上原文]

Although the basic algorithm is the same, there are many ways of finding the shortest path in a DAG, and, by extension, solving most DP problems. You could do it recursively, with memoization, or you could do it iteratively, with relaxation. For the recursion, you could start at the first node, try various “next steps,” and then recurse on the remainder, or (if you graph representation permits) you could look at the last node and try “previous steps” and recurse on the initial part. The former is usually much more natural, while the latter corresponds more closely to what happens in the iterative version.

Now, if you use the iterative version, you also have two choices: you can relax the edges out of each node (in topologically sorted order), or you can relax all edges into each node. The latter more obviously yields a correct result but requires access to nodes by following edges backward. This isn’t as far-fetched as it seems when you’re working with an implicit DAG in some nongraph problem. (For example, in the longest increasing subsequence problem, discussed later in this chapter, looking at all backward “edges” can be a useful perspective.)

Outward relaxation, called reaching, is exactly equivalent when you relax all edges. As explained, once you get to a node, all its in-edges will have been relaxed anyway. However, with reaching, you can do something that’s hard in the recursive version (or relaxing in-edges): pruning. If, for example, you’re only interested in finding all nodes that are within a distance r, you can skip any node that has distance estimate greater than r. You will still need to visit every node, but you can potentially ignore lots of edges during the relaxation. This won’t affect the asymptotic running time, though (Exercise 8-6).

Note that finding the shortest paths in a DAG is surprisingly similar to, for example, finding the longest path, or even counting the number of paths between two nodes in a DAG. The latter problem is exactly what we did with Pascal’s triangle earlier; the exact same approach would work for an arbitrary graph. These things aren’t quite as easy for general graphs, though. Finding shortest paths in a general graph is a bit harder (in fact, Chapter 9 is devoted to this topic), while finding the longest path is an unsolved problem (see Chapter 11 for more on this).

OK，希望我把动态规划讲清楚了，总结下：动态规划其实就是一个连续决策的过程，每次决策我们可能有多种选择(二项式系数和0-1背包问题中我们只有两个选择，DAG图的单源最短路径中我们的选择要看点的出边或者入边，矩阵链乘问题中就是矩阵链可以分开的位置总数…)，我们每次选择最好的那个作为我们的决策。所以，动态规划的时间复杂度其实和这两者有关，也就是子问题的个数以及子问题的选择个数，一般情况下动态规划算法的时间复杂度就是两者的乘积。

Start example Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

Professor Stewart is given the tree that describes the structure of the corporation, using the left-child, right-sibling representation described in Section 10.4. Each node of the tree holds, in addition to the pointers, the name of an employee and that employee’s conviviality ranking. Describe an algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guests. Analyze the running time of your algorithm.

dp[i][0]表示不选i结点时，i子树的最大价值

dp[i][1]表示选i结点时，i子树的最大价值

dp[i][0] = sum(max(dp[u][0], dp[u][1])) $\quad$ (如果不选i结点，u为结点i的儿子)

dp[i][1] = sum(dp[u][0]) + val[i] $\quad$ (如果选i结点，val[i]表示i结点的价值)