Algo-DP

The rod-cutting problem (1-D)

pseudocode 

1
2
3
4
5
6
7
8
9
10
Bottom-up-cut-rod(p,n)
	let r[0..n] and s[0..n] be new arrays
	r[0] ← 0
	for j ← 1 to n do //compute r[j]
		r[j] ← -∞
		for i ← 1 to j do 
		  if r[j] < p[i] + r[j-i]
			  r[j] ← p[i] + r[j-i]
			  s[j] ← i
	return r and s

in python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
INF = 1000000

def rod-cutting(p,n):
	r = [None] * (n+1)
	s = [None] * (n+1)
	for j in range(1,n+1):
		r[j] = -INF
		for i in range(1,j+1):
			if r[j] < p[i] + r[j-i]:
				r[j] = p[i] + r[j-i]
				s[j] = i
	return r, s

if __name__ == '__main__':
	p = [0, 2, 5, 6, 9, 11, 16, 17, 20, 22, 24, 25]
	print(rod-cutting(p,9))

Matrix-chain multiplication (2-D)

Iteration

pseudocode

1
2
3
4
5
6
7
8
9
Matrix-chain-order(p)    //bottom-up
	for i ← 1 to n 
		m[i,i] = 0
	for l ← 2 to n 
		for i ← 1 to n-l+1 do
			j ← i+l-1
			m[i,j] = ∞
			for k ← i to j-1 do
				q ← m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]

in python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
INF = 1000000

def matrix_chain(p):
	n = len(a)
	m = [[None] * n for row in range(n+1)]
	s = [[None] * n for row in range(n+1)]
	for i in range(n+1):
        m[i][i] = 0
	for l in range(2,n+1):
        for i in range(1,n-l+2):
            j = i+l-1
            m[i][j] = INF
            for k in range(i,j):
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
                print(m)
    return m[n-1][n-1]

if __name__ == '__main__':
	a = [2, 3, 5, 4, 2]
	print(matrix_chain(a))

Recursive

pseudocode

1
2
3
4
5
6
7
8
9
Recursive-matrix-chain(p,i,j)   //Top-down
	if i = j then return 0
	m[i,j] = ∞
	for k ← i to j-1 do
		q ← Recursive-matrix-chain(p,i,k) 
				+ Recursive-matrix-chain(p,k+1,j) 
				+ p[i-1]*p[k]*p[j]
		if q < m[i,j] then m[i,j] ← q
	return m[i,j]

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
INF = 1000000

def matrix_chain_recursive(p,i,j):
    n = len(p)
    m = [[None] * n for row in range(n)]
    s = [[None] * n for row in range(n)]
    if i == j:
        return 0
    m[i][j] = INF
    for k in range(i,j):
        q = matrix_chain_recursive(p,i,k) + matrix_chain_recursive(p,k+1,j) \
            + p[i]*p[k+1]*p[j+1]
        if q < m[i][j]:
            m[i][j] = q
    return m[i][j]



if __name__ == '__main__':
	a = [2, 3, 5, 4, 2]
    b = len(a)
    print(matrix_chain_recursive(a,0,b-1))

Memoization

1
2
3
4
Memoized-matrix-chain(p)
	for i ← 1 to n do
		for j ← i to n do m[i,j] = ∞
	return Look-up-chain(m,p,1,n)
1
2
3
4
5
6
7
8
9
10
Look-up-chain(m,p,i,j)
	if m[i,j] < ∞ then return m[i,j]
	if i == j then m[i,j] ← 0
						else
								for k ← i to j-1 do
										q ← Look-up-chain(m,p,i,k) 
												+ Look-up-chain(m,p,k+1,j)
												+ p[i-1]*p[k]*p[j]
										if q < m[i,j] then m[i,j] ← q
	return m[i,j]

Longest common subsequence (LCS)

pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LCS(X,Y)
	m = X.length
	n = Y.length
	Let s[0..m,0..n], r[0..m,0..n] be new arrays
	for i ← 0 to n
		s[0,i] = 0
	for i ← 1 to m
		s[i,0] = 0
		for j ← 1 to n
			if x[i] == y[j]
				s[i,j] = s[i-1,j-1]+1
				r[i,j] = "↖"
			else if s[i-1,j] ≧ s[i,j-1]   //上面優先
				s[i,j] = s[i-1,j]
				r[i,j] = "↑"
			else s[i,j] = s[i,j-1]
				r[i,j] = "←"
	return s, r

python

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
def LCS(x,y):
    m = len(x)
    n = len(y)
    s = [[None] * (n+1) for row in range(m+1)]
    r = [[None] * (n+1) for row in range(m+1)]
    for i in range(n+1):
        s[0][i] = 0
    for i in range(1,m+1):
        s[i][0] = 0
        for j in range(1,n+1):
            if x[i-1] == y[j-1]:
                s[i][j] = s[i-1][j-1] + 1
                r[i][j] = "↖"
            elif s[i-1][j] >= s[i][j-1]: #上面優先
                s[i][j] = s[i-1][j]
                r[i][j] = "↑"
            else: 
                s[i][j] = s[i][j-1]
                r[i][j] = "←"
    return s, r


if __name__ == '__main__':
    x = ['G', 'T', 'C', 'A' ]
    y = ['G', 'T', 'A', 'C', 'G']
    print(LCS(x,y))

OBST

pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
OBST(p,q,n)
	let s[1..n+1,0..n], w[1..n+1,0..n], root[1..n,1..n]
	for i ← 1 to n+1     //第一波斜線
		s[i,i-1] = q[i-1]
		w[i,i-1] = q[i-1]
	for l ← 1 to n
		for i ← 1 to n-l+1
			j = i+l-1
			s[i,j] = ∞
			w[i,j] = w[i,j-1] + p[j] + q[j]
			for r ← i to j
				t = s[i,r-1] + s[r+1,j] + w[i,j]
				if t < s[i,j]
					s[i,j] = t
					root[i,j] = r
	return s, root

python

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
INF = 100000

def OBST(p, q, n):
    s = [[None] * (n+1) for row in range(n+2)]
    w = [[None] * (n+1) for row in range(n+2)]
    root = [[None] * (n+1) for row in range(n+1)]
    for i in range(1,n+2):
        s[i][i-1] = q[i-1]
        w[i][i-1] = q[i-1]
    for l in range(1,n+1):
        for i in range(1,n-l+2):
            j = i+l-1
            s[i][j] = INF
            w[i][j] = w[i][j-1] + p[j] + q[j]
            for r in range(i,j+1):
                t = s[i][r-1] + s[r+1][j] + w[i][j]
                if t < s[i][j]:
                    s[i][j] = t
                    root[i][j] = r
    return s, root

if __name__ == '__main__':
    p = [0, 5, 2, 4, 3]
    q = [3, 2, 3, 4, 2]
    n = len(p) - 1
    print(OBST(p, q, n))
Learning Note
#Algorithm #python
Algo-DP
http://example.com/2021/11/07/Algo-DP/
Author
Xiung
Posted on
November 7, 2021
Licensed under