Introduction to Dynamic Programming

Dynamic programming

In this chapter, we’ll implement various dynamic programming algorithms and see how they solve problems that evaded all attempts to solve them using greedy or divide-and-conquer strategies. There are countless applications of dynamic programming in practice, ranging from searching for similar internet pages to gene prediction in DNA sequences. We’ll learn how the same idea helps automatically make spelling corrections and finds the differences between two versions of the same text.

---

Money change

Compute the minimum number of coins needed to change the given value into coins with denominations $1$, $3$, and $4$.

Input: An integer $money$.

Output: The minimum number of coins with denominations $1$, $3$, and $4$ that change $money$.

---

Primitive calculator

Find the minimum number of operations needed to get a positive integer $n$ from $1$ using only three operations: add $1$, multiply by $2$, and multiply by $3$.

Input: An integer $n$ ...