Introduction

Loved and feared in equal measure by many programmers, dynamic programming (DP) is a conceptual extension of the divide-and-conquer paradigm that pertains to a specific class of problems. The difficulties involved in dynamic programming problems are multi-faceted and often require creativity, patience, and the ability to visualize abstract concepts. However, the challenges these problems pose frequently have elegant and surprisingly simple solutions, which can provide a programmer with insights that reach far beyond the scope of the immediate task.

In the previous chapter, we discussed several techniques, such as the divide-and-conquer and the greedy approach. These approaches, though quite effective in the right circumstances, will not produce optimal results in certain situations. For example, in the previous chapter, we discussed how Dijkstra's algorithm does not produce optimal results for graphs with negative edge weights, whereas the Bellman-Ford algorithm does. For...