A road named NoNameUno

In DP3 we talked about recursive implementation for minimal coins needed for a given change amout.

Recursive algorithm is best seen as top-down tree. Drawing that tree for small sample shows there are redundant computations of sub-problems. So we need to store intermediate solution to sub-problems.

In general, Understanding the substructures and their relations to Original problem is the key.

DP problems have many classifications like: Dimensions, Stages, Deterministic vs. Non-deterministics. So understanding the structure and relate to some category is really a key insight.

During this process of trying and explaining DP problems and theirs' possible solutions I will try to cover as much as I could. But my main goal is to get to Stochastics Dynamic Programming.

Example:

We know shortest path in terms of distance or time is one such deterministic DP problem. None other than Bellman ( inventor of DP ) showed the solution using DP method.

Now lets turn around and think like ---

There is a roadway network from San Francisco, CA to Tempa,Florida. Further assume that there is a probability associated with any segment of the trip could be under construction, hence not accessible. Now the Question is how could I take the most viable route to get to the destination.

Another one, Suppose you expect N offers on your house on sale, and there a probablity associated with the i_th offer being the best offer. P(i) = Probability that the i_th offer is the best offer so far to accept and terminate the consideration process and H(i) = Probablity that it would be best to reject the offer to realize better gain later.

Above problems are some of the examples of - Stochastic Dynamic Programming.