Loop Invariants:
Precondition(s): m and s have been defined
Postcondition(s): m[i,j] gives the cost of the optimal parenthisization of p[i...j] and
	s[i...j] contains the value k at which we split p[i...j] in an optimal parenthisization

Recursive(p):
1	n = p.length-1
2	let m[1...n,1...n] and s[1...n-1,2...n] be new tables
3	Recursive-Matrix-Chain(p,1,n)
4	return m and sPrecondition(s): none

Recursive-Matrix-Chain(p,i,j)
1	if i == j
2		return 0
3	m[i,j] = infinity
4	for k = i to j-1
5		q = Recursive-Matrix-Chain(p,i,k)
			+ Recursive-Matrix-Chain(p,k+1,j)
			+ p[i-1]p[k]p[j]
6		if q < m[i,j]
7			m[i,j] = q
8			s[i,j] = k
9	return m[i,j]

Loop Invariant:
	At the start of each iteration of the for loop on lines 4-8, m[i,j] contains the cost of the optimal parenthesization of p[i...k]
Initialization: Before the first iteration of the loop, when k=i, m[i,j] trivially contains the optimal parenthisization of p[i...i], since it has none, and m[i,j] = infinity

Maintenance:
	During each iteration of the loop, q = the sum of the cost of the optimal parenthisization of p[i...k] and p[k+1...j] + p[i-1]*p[k]*p[j], which is the cost of the parenthization separated at k. If this value is less than the previous value of m[i,j], m[i,j] is set to q, making m[i,j] the cost of the optimal parenthesization of p[i...k+1]. when k is incremented, the loop invariant is satisfied.

Termination:
	After the final iteration of the loop, m[i,j] contains the cost of the optimal parenthesization of p[i...j]
Matrix-Chain-Order(p)
1	n = p.length-1
2	let m[1...n,1...n] and s[1...n-1,2...n] be new tables
3	for i = 1 to n
4		m[i,i] = 0
5	for l = 2 to n
6		for i = l to n-l+1
7			j = i+l-1
8			m[i,j] = infinity
9			for k = i to j-1
10				q = m[i,j] + m[k+1,j] + p_i-1 * p_k * p_j
11				if q < m[i,j]
12					m[i,j] = q
13					s[i,j] = k
14	return m and s

Loop Invariant: At the start of each iteration of the for loop on lines 5-13,
m[1..l-1][1..l-1] contain the correct minimum costs of the parenthesization


Initialization:
	Before the start of the first loop, l==2.
Plugging into the loop invariant, we get m[1..1][1..1] contain the correct minimum
That range was initialized to 0 in the for loop on 3-4. Since m[1][1] does not contain a matrix, 0 is correct
Maintenance:
	Within each iteration of the loop on lines 6-13, the loop on lines 9-13
set the correct cost of m[i][j] for m[l..n-l+1][n+l-1]. L is then increased by 1, knowing that m[1..l-1][1..l-1] is maintained.

Termination:
	At the end of the for loop, l = n. Plugging into the loop invariant, we get m[1..n-1][1..n-1] contains the correct minium costs. The minimum cost for the whole input and the output of the algorithm is located in m[1][n-1]. Therefore this algorithm is correct.Precondition(s): none
Postcondition(s): m gives the cost of the optimal parenthisization of p and s contains the value of k at which we split p in an optimal parenthisization


Memoized-Matrix-Chain(p)
1	n = p.length - 1
2	let m[1...n, 1...n] be a new table
3	for i = 1 to n
4		for j = i to n
5			n[i,j] = infinity
6	return Lookup-Chain(m,p,l,n)


Precondition(s): m and s have been defined
Postcondition(s): m[i,j] gives the cost of the optimal parenthisization of p[i...j] and
	s[i...j] contains the value k at which we split p[i...j] in an optimal parenthisization

Lookup-Chain(m,p,i,j)
1	if m[i,j] < infinity
2		return m[i,j]
3	if i == j
4		m[i,j] = 0
5	else for k = i to j-1
6		q = Lookup-Chain(m,p,i,k)
			+ Lookup-Chain(m,p,k+1,j) + p_i-1 * p_k * p_j
7		if q < m[i,j]
8			m[i,j] = q
9	return m[i,j]

Loop Invariant:
	At the start of each iteration of the for loop on lines 5-8, m[i,j] contains the cost of the optimal parenthesization of p[i...k]
Initialization: Before the first iteration of the loop, when k=i, m[i,j] trivially contains the optimal parenthisization of p[i...i], since it has none, and m[i,j] = infinity

Maintenance:
	During each iteration of the loop, q = the sum of the cost of the optimal parenthisization of p[i...k] and p[k+1...j] + p[i-1]*p[k]*p[j], which is the cost of the parenthization separated at k. If this value is less than the previous value of m[i,j], m[i,j] is set to q, making m[i,j] the cost of the optimal parenthesization of p[i...k+1]. when k is incremented, the loop invariant is satisfied.

Termination:
	After the final iteration of the loop, m[i,j] contains the cost of the optimal parenthesization of p[i...j]