dynamic programming
Summary
Top-down/memoization
Memo = empty table
Solve(state):
if state is a base case:
return base value
if Memo[state] has been computed:
return Memo[state]
answer = initial value
for each valid choice:
candidate = combine(
contribution of choice,
Solve(smaller state determined by choice)
)
answer = update(answer, candidate)
Memo[state] = answer
return answer
return Solve(target state)
Bottom-up/tabulation
create table DP
initialize base cases
for each non-base state in dependency order:
DP[state] = initial value
for each valid choice:
candidate = combine(
contribution of choice,
DP[smaller state determined by choice]
)
DP[state] = update(DP[state], candidate)
return DP[target state]
dependency order is an important thing to take note of
Concept
Dynamic programming
Fibonacci numbers
- toy example
- linear DP
- recursive calls that depend on other recursive calls/the base case(s)
fib(5),
cpp
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return f(n - 1) + f(n - 2);
}
Fibonacci by DP
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| no choice: both values are required |
Top-down fibonacci
- recursive function + memoization
fib(5)with memoization,
cpp
const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];
int fib(int n) {
if (found[n]) return memo[n];
if (n == 0) return 0;
if (n == 1) return 1;
found[n] = true;
return memo[n] = f(n - 1) + f(n - 2);
}
Correctness
- induction
Time complexity
additions
an aside, not covered in
cs341, since the size of the numbers grows, addition becomes significant
Bottom-up fibonacci
- start with the basecase
- uses tabulation instead of memoization
- possibly reduce space complexity, but values need to be relaculated every function call
cpp
const int MAX_SAVE = 3; // only the previous, O(1) space
int fib[MAX_SAVE];
int f(int n) {
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];
return fib[n % MAX_SAVE];
}