Dynamic programming is a style of algorithmic problem solving for finding optimal solutions. Where you have to make a sequence of decisions, and where the remaining problem after making the first decision is an instance of the original problem, you can solve the smaller problem recursively and combine solutions to get the final answer. Dynamic programming was first developed by Richard Bellman in the 1950s and has found applications in engineering and economics, for example in the field of control theory. A step-by-step process can be employed in dynamic programming. 1. Identify the optimal substructure of the problem 2. Find a recurrence for the optimal value (also called value function or "cost-to-go") 3. Memoize intermediate solutions (to avoid duplicate work) 4. Recover final solution from memo table ## optimal substructure A problem has optimal substructure if, after making a decision, making the next decision optimally is a subset of the original problem. This substructure is overlapping, whereas if it were not overlapping a [[greedy algorithm]] could be used. For example, imagine you need to cut a rod to maximize profit based on different prices for different rod sizes. After making a cut, the optimal decision will be based solely on the amount of rod you have now. ## recurrence An example recurrence for the general form of a maximization problem is $maxSoFar(t) = \begin{cases} 0 & t = 0 \\ -\inf & t <0 \\ \max\begin{cases} V_j + maxSoFar(t - j) \\ maxSoFar(t))\end{cases} \end{cases} $ where $t$ is the target, $t - j$ is what remains after the $j^{th}$ decision, and $V_j$ is the value of the $j^{th}$ decision. Here you can make any of the $j$ decisions available or do nothing. When target is reduced to $0$, we've reached a base case. If a decision results in a negative value of target (which is not permissible in this example), the penalty is very high. Considering the rod cutting problem, $t$ is the rod length and $V_j$ must be provided. Until the rod is exhausted, we can make a cut of some length and take the corresponding value or not cut. ## memoization In memoization, a [[hash table]] is sometimes used but when the keys of the table (e.g., targets $t$) can be known in advance, a basic table is much more efficient. For each index $t$, record the value provided by $maxSoFar(t)$. The direction in which the table is filled is important and should be inferred from the recurrence. ## solution recovery While recording the memo table, record in a parallel table the decision that was made. To recover the solution, read from the opposite direction the table was filled. The next cell to be read will be given by $S[t - j]$. The [[coin changing problem]] and [[knapsack problem]] are canonical examples of dynamic programming. [[Longest common subsequence]] is a real-world example important to genetics. Under certain conditions, a [[greedy algorithm]] will return the same solution as the dynamic programming algorithm, and will be computationally easier. The [[coin changing problem]], depending on the denominations, is one example. > [!Tip]- Additional Resources > - [Dynamic Programming isn't hard... | DecodingIntuition (YouTube)](https://youtu.be/gK8KmTDtX8E?si=9HmM4neQAhPieufh)