Analyze Question

This is a simple example to understand matrix chain order in DP.
As we know, all the DP problem can be solve by three basic criteria

1. find the optimized sub problem

   In matrix multiplication , the cost of multiplication of matrix is different between the different multi sequence.for e.g. we have 3 matrix

   A: 10X100

   B: 100x5

   C: 5x50

   then if we follow diff multiplication sequence

   for ((A1A2)A3) : A1A2=$10\times 100 \times 5 = 5000 $ A3=$10\times5\times50 = 2500$ tot: 7500

   for(A1(A2A3)): A2A3=$100 \times 5 \times 50 = 25000$ A1 = $10\times100\times50=50000$ tot:75000

   and thus its 10 times bigger for the last approach than the first approach

   and in DP we suppose if we already know the best solution for the matrix multiplication, for e.g. (A1A2A3A4)(A5A6A7) , if we separate them into subarrays ((A1A2A3)A4) (A5(A6A7)) the subarray it self should also be the optimized multiplication.

Method:

The Huffman coding which implies the greedy algorithm has its theory:

If you have a set of characters , and called it $C$ , has several characters which may or may not overlap each other.

Then lets say $C$ contains these characters: f,e,d,c,b,a

each character has different frequency which we will called it $F$ . Now we have a sequence like: f(5) ,e(9), d(16), c(12),b(13),a(45)

Now if we want to code these characters in order to get a better compression of the space we stored it , we have two choices

1. we just simply code it into same length code
2. we use the greedy method, which means we do our best to put the higher frequency character into short codes and lower frequency characters into the longer codes