Shruti Speak's

Dynamic programming  (referred to as  DP  ) is a very powerful technique to solve a particular class of problems. It demands elegant formulation of the approach and simple thinking. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again. If the given problem can be broken up into smaller sub-problems and these smaller sub-problems are in turn divided into smaller ones, and in this process, if you observe some over-lapping sub-problems, then its a big hint for DP. Also, the optimal solutions to the sub-problems contribute to the optimal solution of the given problem. There are two ways of doing this. 1.) Top-Down :  Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is

Q.1 The owner of a chain of four grocery stores has purchased six crates of fresh strawberries.The estimated probability distribution of potential sales of the strawberries before spoilage differ among the four stores.The following table gives the estimated total expected profit at each store, when it is allocated various numbers of crates:                                                                     Store                                                                  1          2          3            4                                               ______________________________________                                       0                         0          0          0            0                                       1                         4          2          6            2 Number                                       2                         6          4          8            3 of                                       3