Often web scale problems are large requiring working with big data. Dealing with such cases means breaking problems down into sub-problems. One can often use divide-and-conquer approaches which are applied recursively in context to sorting and searching such as mergesort, quicksort, and binary search. These algorithms work from a top-down fashion. What this implies is that in divide-and-conquer the approach is used to break down problems into sub-problems in order to solve the original problem. However, at times it is necessary to work from bottom-up especially in case of web search. In this approach sub-problems are solved recursively to solve larger problems. As a solution to a sub-problem is found it is stored for later lookup. Again, dynamic programming is useful in domains of advertising and complex distributed analytics on big data. In this respect, one is trying to find the optimal solution. The principle holds when every optimal solution to a problem pretty much contains optimal solutions to all sub-problems. However, the reverse is not the case. A typical problem to dynamic programming is the knapsack problem which does not work well with a greedy approach. Although, dynamic programming is not appropriate for all problems it does offer a very useful optimization strategy to solving very complex situations which ordinarily would take exponential time to solve for optimality.
AMP
AMP
