Topic
Dynamic Programming
A collection of 6 issues
Longest Common Subsequence
Subset Sum Problem
A special case of 0/1 Knapsack Problem.
Given a finite set \(S = \{ s \in \mathbb{Z}_+\}\) and an integer \(t < 0\), is there a subset
Partition Problem
A special case of Subset Problem.
Levenshtein Distance
#include <algorithm>
#include <vector>
class LevenshteinDistance {
std::vector<char> sequence1_;
std::vector<char> sequence2_;
public:
LevenshteinDistance(std::vector<char>& sequence1, std::vector<char>& sequence2) {
sequence1_ = sequence1;
sequence2_ = sequence2;
}
int Distance();
};
int LevenshteinDistance::Distance() {
int sequence1_size
The Coin Change Problem
The coin change problem is a classic dynamic programming problem (unbounded knapsack problem) which can be solved recursively.
N = Coins with different denominations
D = Array of denominations
S = Total amount to make
C = Number of Combinations
Recursive Formula:
C(N, S) = C(N - 1, S) + C(N, S -