Overview

Dynamic programming is an algorithmic design paradigm which solves for optimization. Dynamic programming focuses on making the globally optimal solution from multiple choices.

Methods of creating a dynamically programmatic solution focuses on breaking down the problem into repeatable parts and solving subproblems to construct the optimal solution.

An optimization problem should have two key elements for a dynamic programming algorithm to apply.

• Optimal substructure: Each subproblem contains an optimal solution.
• Overlapping subproblems: The space of the actual subproblems is small, which means a recursive algorithm can solve the same subproblem instead of new subproblems.

Generally a dynamic programming algorithm can be created with the following steps.

1. Prove an optimal substructure
2. Provide a recursive formulation
3. Fill up a table
4. Construct the optimal solution

Top-Down Approach

This approach focuses on recursively solving the problem in a more natural manner (top-down). Memoization is used to save the result of each subproblem.

The top down approach first checks to see if a subproblem has been solved, or memoized. If it has then it simply returns the saved result, otherwise it calculates the result normally.

Properties:

• Sometimes (rarely) has a better running time when it does not need to examine all possible subproblems.
• Same asymptotic running time as #Bottom-Up Approach

Bottom-Up Approach

This focuses on solving "smaller" subproblems. The solution is organized in such a way that subproblems are solved in "size" order, smallest first. The solution to each subproblem is then stored after it is first solved.

Properties:

• Better constant factors (usually) as it avoids recursive function calls that incur additional overhead.

• Same asymptotic running time as #Top-Down Approach

This is commonly done using arrays or with variable swapping/shifting

"""
This approach uses an array and iteratively builds the solution.
We use an array (list) to store the previous two values.

This becomes an issue if we decide to calculate arbitrarily large Fibbonaci numbers, however.
"""
def fib(n: int) -> int:
    if n <= 1
        return n
    # Create an array (list) to add previous values to
    prev = [1, 1]
    for i in range(2, n):
        # Use from out list of previous values
        new = prev[i - 1] + prev[i - 2]
        prev.append(new)
    return prev[n - 1]
        

Definitions

Memoization

Memoization not to be confused with memorization is technique of saving the results of a calculation to be looked up later. This is useful when solving dynamic programming problems where subproblems can repeat.

Reference

1. Sun, Hongyang Various Lectures The University of Kansas 2024

Related

• Algorithms