dynamic programming

Work in Progress

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 fibonacci

  • 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);
}
543210121032101

Fibonacci by DP

StateMeansNeedDecisionCombination
is the -th Fibonacci number. and .no choice: both values are required. Bases: .

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);
}
012345

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];
}