Lecture 9
Tuesday, June 6, 2017
10:37 PM
C(i,j) = cost of cell (i,j)
2
8
9
5
8
4
4
6
2
3
5
7
5
6
1
3
2
5
4
8
can move 
Directly above, or
Above Left, or
Above Right.
Goal:  Get from the first (bottom) row to the last (top) row via a cheapest path. 
Cost of a path = sum of costs of the cells on the path.
Template:
(1) Describe an array of values (numbers) to compute. Each array entry corresponds to a sub-problem of the original problem.
(2) Give a recurrence to compute the values in the array: a "big" problem can be solved using the solutions to some "small" sub-problems.
(3) Give a program to compute the array values: a "bottom-up" algorithm. 
(4) Using the array values, compute an optimal solution to the original problem.
2
8
9
5
8
4
4
6
2
3
5
7
5
6
1
3
2
5
4
8
13
19
16
12
15
11
11
13
7
8
7
9
7
10
5
3
2
5
4
8
DP Algorithm
(1) Array:  Define  M[j]  = the value of an optimal solution for the subset of jobs 1,…, j
(2) Recurrence:  Two possibilities: (a) either job  j  is part of an optimal solution,
                                                         or (b) job  j  is not.
      Hence, either  M[j] = v[j] + M[p(j)], or
                                M[j] = M[j-1].
      So, the recurrence is
                              M[0]=0
                              M[j] = max{ v[j] + M[p(j)] , M[j-1] }
(3) Algorithm to fill in the array:   M[ 0 ] = 0
                                                            for  j=1 to n 
                                                                   M[ j ] = max { v[j] + M[ p(j) ],  M[j-1] }
                                                            end for
(4) Recover an actual optimal schedule from M[]:  