This is an old revision of the document!
6.2. Principles of Dynamic Programming: Memoization or iteration over Subproblems
Designing the Algorithm
The key to the efficient solution found by Memoization is the array M that keeps track of the previously computed solutions. Once we have the array M, the problem is solved: M[n] contains the value of the optimal solution on the full instance and Find-Solution can be used to trace back through M efficiently and return an optimal solution.
Algorithm
Iterative-Compute-OPT
M[0] = 0
For j = 1,2,…,n
M[j] = max(vj + M[p(j)],M[j-1])
Endfor
