Dynamic Programming:  Intelligent Trial and Error  (You are still trying essentially every possible combination, but doing it efficiently and avoiding repeated work.)

The most famous application of dynamic programming is optimization, meaning what is the best way to do something, to minimize or maximize a certain value.

MATRIX-CHAIN-MULTIPLICATION

The classic algorithm for multiplying matrices [m x n] [n x p] ==> [m x p] involves finding the inner product of each row of the first matrix with each column of the second.  It takes mnp multiplications.


1  2
3  4             1 -1 0
5  6             1 -1 0



3  -3  0
7  -7  0
11 -11 0






[3  x 4][4 x 2][2 x 6]



([3 x 4][4 x 2]) [2 x 6]

     24

   [3 x 2][2 x 6]
      36
   [3x6]

Total:  60


[3 x 4] ([4 x 2][2 x 6])

            48
  [3x4]         [4x6]
            72
         [3x6]
Total:    120

((( A B)( C (D E)))((F ((G H) I)) J))


   0      1      2      3        4      5
[5 x 2][2 x 7][7 x 9][9 x 12][12 x 8][8 x 2]  ==>  5 x 2



   0      1      2      3        4      5

0  0     70     216     462


1         0     126     342     534


2                0      756


3                       0      864      408


4                                0      192


5                                       0

How many multiplies does it take to compute the chain beginning at the row number and ending at the column number