Dynamic programming explained
What dynamic programming is, memoization vs bottom-up tables, and how to recognize DP problems like coin change, LCS and knapsack.
Dynamic programming (DP) solves a problem by combining answers to smaller versions of it, computing each smaller answer only once. It applies when a problem has:
- overlapping subproblems: a plain recursive solution asks the same questions over and over, and
- optimal substructure: the best answer is built from the best answers to smaller questions.
There are two ways to write it:
- Memoization (top-down): write the recursion, and cache each result in a table the first time it's computed.
- Tabulation (bottom-up): fill the table from the smallest questions up, in an order where everything an entry needs is already there.
The recipe: decide what one table entry means, write how it's built from smaller entries, set the base cases, and pick a filling order. Classic DP problems include Fibonacci, coin change, grid paths, longest common subsequence (the heart of diff), the 0/1 knapsack and edit distance.
Example
#include <iostream>
#include <vector>
// Fewest coins that add up to amount, or -1 if it can't be done.
int min_coins(const std::vector<int>& coins, int amount) {
const int IMPOSSIBLE = amount + 1;
std::vector<int> best(amount + 1, IMPOSSIBLE);
best[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
return best[amount] == IMPOSSIBLE ? -1 : best[amount];
}
int main() {
std::cout << min_coins({1, 3, 4}, 6) << " " << min_coins({2}, 3) << "\n";
return 0;
}
Output:
2 -1