Last modified: September 23, 2024

This article is written in: 🇺🇸

Dynamic Programming

Dynamic Programming (DP) is a fundamental algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems. The core idea is to solve each subproblem only once and store its solution—typically using a memory-based data structure (array, table, or map)—thus avoiding the computational overhead of recomputing the same solutions multiple times. This approach is particularly powerful for problems exhibiting the properties of optimal substructure and overlapping subproblems.

Originally developed by Richard Bellman in the 1950s, dynamic programming has since become an essential tool in fields such as computer science, economics, and operations research. It provides a structured approach to problem-solving that can transform exponential-time algorithms into polynomial-time solutions, greatly improving computational efficiency.

Fundamental Principles of Dynamic Programming

To effectively apply dynamic programming, a problem must satisfy two key properties:

1. Optimal Substructure

Definition: A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. Formally, if the optimal solution $S_n$ for problem size $n$ can be constructed from optimal solutions $S_k$ for smaller sizes $k < n$, then the problem has an optimal substructure.

Mathematical Representation:

Consider a problem where we want to find the optimal value $V(n)$ for a given parameter $n$. If there exists a function $f$ such that:

$$ V(n) = \min_{k} { f(V(k), V(n - k)) } $$

then the problem exhibits optimal substructure.

Example: Shortest Path in Graphs

In the context of graph algorithms, suppose we want to find the shortest path from vertex $A$ to vertex $C$. If $B$ is an intermediate vertex on the shortest path from $A$ to $C$, then the shortest path from $A$ to $C$ is the concatenation of the shortest path from $A$ to $B$ and the shortest path from $B$ to $C$.

2. Overlapping Subproblems

Definition: A problem has overlapping subproblems if it can be broken down into subproblems that are reused multiple times. This means that the recursive solution involves solving the same subproblem repeatedly.

Mathematical Representation:

Let $S(n)$ be the set of subproblems for problem size $n$. If there exists $s \in S(n)$ such that $s$ appears in $S(k)$ for multiple $k$, the problem has overlapping subproblems.

Example: Fibonacci Numbers

The recursive computation of Fibonacci numbers $F(n) = F(n - 1) + F(n - 2)$ involves recalculating the same Fibonacci numbers multiple times. For instance, to compute $F(5)$, we need to compute $F(4)$ and $F(3)$, both of which require computing $F(2)$ and $F(1)$ multiple times.

Dynamic Programming Techniques

There are two primary methods for implementing dynamic programming algorithms:

1. Memoization (Top-Down Approach)

Concept: Memoization involves solving the problem recursively while storing the results of solved subproblems in a data structure (typically a hash table or array). Before computing a subproblem, the algorithm checks if the result is already known and returns the cached result if it is.

Algorithm Steps:

  1. Identify the parameters that uniquely define a subproblem and create a recursive function using these parameters.
  2. Establish base cases to terminate recursion.
  3. Initialize a data structure to store computed subproblem results.
  4. Before computing a subproblem, check if its result is already stored.
  5. If not already computed, compute the subproblem's result and store it.

Example: Computing Fibonacci Numbers with Memoization

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

Analysis:

2. Tabulation (Bottom-Up Approach)

Concept: Tabulation involves solving all smaller subproblems first and then combining them to solve larger subproblems. It typically uses iteration and a table (array) to store solutions to subproblems, building up to the solution of the original problem.

Algorithm Steps:

  1. Initialize the table by setting up a structure to store the results of subproblems, and ensure that base cases are properly initialized to handle the simplest instances of the problem.
  2. Iterative computation is carried out using loops to fill the table, making sure that each subproblem is solved in the correct order before being used to solve larger subproblems.
  3. Construct the solution by referencing the filled table, using the stored values to derive the final solution to the original problem efficiently.

Example: Computing Fibonacci Numbers with Tabulation

def fibonacci(n):
    if n <= 1:
        return n
    fib_table = [0] * (n + 1)
    fib_table[0], fib_table[1] = 0, 1
    for i in range(2, n + 1):
        fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
    return fib_table[n]

Analysis:

Comparison of Memoization and Tabulation

Aspect Memoization (Top-Down) Tabulation (Bottom-Up)
Approach Recursive Iterative
Storage Stores solutions as needed Pre-fills table with solutions to all subproblems
Overhead Function call overhead due to recursion Minimal overhead due to iteration
Flexibility May be easier to implement for complex recursive problems May require careful ordering of computations
Space Efficiency Potentially higher due to recursion stack and memoization Can be more space-efficient with careful table design

Implementation Techniques with Mathematical Rigor

Dynamic programming problems are often formulated using recurrence relations, which express the solution to a problem in terms of its subproblems.

Formulating Recurrence Relations

Example: Longest Common Subsequence (LCS)

Given two sequences $X = x_1, x_2, ..., x_m$ and $Y = y_1, y_2, ..., y_n$, the length of their LCS can be defined recursively:

$$ LCS(i, j) = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ LCS(i - 1, j - 1) + 1 & \text{if } x_i = y_j \\ \max(LCS(i - 1, j), LCS(i, j - 1)) & \text{if } x_i \neq y_j \end{cases} $$

Implementation:

We can implement the LCS problem using either memoization or tabulation. With tabulation, we build a two-dimensional table $LCS[0..m][0..n]$ iteratively.

State Representation

Properly defining the state is crucial for dynamic programming.

Example: 0/1 Knapsack Problem

$$ dp[i][w] = \begin{cases} dp[i - 1][w] & \text{if } w_i > w \\ \max(dp[i - 1][w], dp[i - 1][w - w_i] + v_i) & \text{if } w_i \leq w \end{cases} $$

Implementation:

We fill the table $dp[0..n][0..W]$ iteratively based on the state transition.

Advanced Dynamic Programming Concepts

Memory Optimization

In some cases, we can optimize space complexity by noting dependencies between states.

Example: Since $dp[i][w]$ depends only on $dp[i - 1][w]$ and $dp[i - 1][w - w_i]$, we can use a one-dimensional array and update it in reverse.

dp = [0] * (W + 1)
for i in range(1, n + 1):
    for w in range(W, w_i - 1, -1):
        dp[w] = max(dp[w], dp[w - w_i] + v_i)

Dealing with Non-Overlapping Subproblems

If a problem does not have overlapping subproblems but does have optimal substructure, it may be more appropriate to use Divide and Conquer rather than dynamic programming.

Example: Merge Sort algorithm divides the list into halves, sorts each half, and then merges the sorted halves.

Common Terms in Dynamic Programming Context

Recursion

Definition: A process where a function calls itself directly or indirectly to solve a smaller instance of the same problem until it reaches a base case.

Mathematical Perspective:

A recursive function $f(n)$ satisfies:

$$ f(n) = g(f(k), f(n - k)) $$

for some function $g$ and smaller subproblem size $k < n$.

Example: Computing $n!$:

$$ n! = n \times (n - 1)! $$

with base case $0! = 1$.

Subset

Definition: For a set $S$, a subset $T$ is a set where every element of $T$ is also an element of $S$. Denoted as $T \subseteq S$.

Mathematical Properties:

Relevance to DP:

Subsets often represent different states or configurations in combinatorial problems, such as the subset-sum problem.

Subarray

Definition: A contiguous segment of an array $A$. A subarray is defined by a starting index $i$ and an ending index $j$, with $0 \leq i \leq j < n$, where $n$ is the length of the array.

Mathematical Representation:

$$ \text{Subarray } A[i..j] = [A_i, A_{i+1}, ..., A_j] $$

Example:

Given $A = [3, 5, 7, 9]$, the subarray from index $1$ to $2$ is $[5, 7]$.

Relevance to DP:

Subarray problems include finding the maximum subarray sum (Kadane's algorithm), where dynamic programming efficiently computes optimal subarrays.

Substring

Definition: A contiguous sequence of characters within a string $S$. Analogous to subarrays in arrays.

Mathematical Representation:

A substring $S[i..j]$ is:

$$ S_iS_{i+1}...S_j $$

with $0 \leq i \leq j < \text{length}(S)$.

Example:

For $S = "dynamic"$, the substring from index $2$ to $4$ is $"nam"$.

Relevance to DP:

Substring problems include finding the longest palindromic substring or the longest common substring between two strings.

Subsequence

Definition: A sequence derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Mathematical Representation:

Given sequence $S$, subsequence $T$ is:

$$ T = [S_{i_1}, S_{i_2}, ..., S_{i_k}] $$

where $0 \leq i_1 < i_2 < ... < i_k < n$.

Example:

For $S = [a, b, c, d]$, $[a, c, d]$ is a subsequence.

Relevance to DP:

The Longest Common Subsequence (LCS) problem is a classic dynamic programming problem.

LCS Dynamic Programming Formulation:

Let $X = x_1 x_2 ... x_m$ and $Y = y_1 y_2 ... y_n$. Define $L[i][j]$ as the length of the LCS of $X[1..i]$ and $Y[1..j]$.

Recurrence Relation:

$$ L[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ L[i - 1][j - 1] + 1 & \text{if } x_i = y_j \\ \max(L[i - 1][j], L[i][j - 1]) & \text{if } x_i \neq y_j \end{cases} $$

Implementation:

We build a two-dimensional table $L[0..m][0..n]$ using the above recurrence.

Time Complexity: $O(mn)$

Practical Considerations in Dynamic Programming

Identifying DP Problems

Not all problems are amenable to dynamic programming. To determine if DP is appropriate:

State Design and Transition

Complexity Optimization

Common Pitfalls

List of Problems

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1. This sequence is a classic example used to demonstrate recursive algorithms and dynamic programming techniques.

Grid Traveler

The Grid Traveler problem involves finding the total number of ways to traverse an m x n grid from the top-left corner to the bottom-right corner, with the constraint that you can only move right or down.

Climbing Stairs

The Climbing Stairs problem requires determining the number of distinct ways to reach the top of a staircase with 'n' steps, given that you can climb either 1, 2, or 3 steps at a time.

Can Sum

The Can Sum problem involves determining if it is possible to achieve a target sum using any number of elements from a given list of numbers. Each number in the list can be used multiple times.

How Sum

The How Sum problem extends the Can Sum problem by identifying which elements from the list can be combined to sum up to the target value.

Best Sum

The Best Sum problem further extends the How Sum problem by finding the smallest combination of numbers that add up to exactly the target sum.

Can Construct

The Can Construct problem involves determining if a target string can be constructed from a given list of substrings.

Count Construct

The Count Construct problem expands on the Can Construct problem by determining the number of ways a target string can be constructed using a list of substrings.

All Constructs

The All Constructs problem is a variation of the Count Construct problem, which identifies all the possible combinations of substrings from a list that can be used to form the target string.

Coins

The Coins problem aims to find the minimum number of coins needed to make a given value, provided an infinite supply of each coin denomination.

Longest Common Subsequence

The Longest Common Subsequence problem involves finding the longest subsequence that two sequences have in common, where a subsequence is derived by deleting some or no elements without changing the order of the remaining elements.

Longest Increasing Subarray

The Longest Increasing Subarray problem involves identifying the longest contiguous subarray where the elements are strictly increasing.

Knuth-Morris-Pratt

The Knuth-Morris-Pratt (KMP) algorithm is a pattern searching algorithm that looks for occurrences of a "word" within a main "text string" using preprocessing over the pattern to achieve linear time complexity.

Minimum Insertions to Form a Palindrome

This problem involves finding the minimum number of insertions needed to transform a given string into a palindrome. The goal is to make the string read the same forwards and backwards with the fewest insertions possible.

Table of Contents

  1. Fundamental Principles of Dynamic Programming
    1. 1. Optimal Substructure
    2. 2. Overlapping Subproblems
  2. Dynamic Programming Techniques
    1. 1. Memoization (Top-Down Approach)
    2. 2. Tabulation (Bottom-Up Approach)
    3. Comparison of Memoization and Tabulation
  3. Implementation Techniques with Mathematical Rigor
    1. Formulating Recurrence Relations
    2. State Representation
  4. Advanced Dynamic Programming Concepts
    1. Memory Optimization
    2. Dealing with Non-Overlapping Subproblems
  5. Common Terms in Dynamic Programming Context
    1. Recursion
    2. Subset
    3. Subarray
    4. Substring
    5. Subsequence
  6. Practical Considerations in Dynamic Programming
    1. Identifying DP Problems
    2. State Design and Transition
    3. Complexity Optimization
    4. Common Pitfalls
  7. List of Problems
    1. Fibonacci Sequence
    2. Grid Traveler
    3. Climbing Stairs
    4. Can Sum
    5. How Sum
    6. Best Sum
    7. Can Construct
    8. Count Construct
    9. All Constructs
    10. Coins
    11. Longest Common Subsequence
    12. Longest Increasing Subarray
    13. Knuth-Morris-Pratt
    14. Minimum Insertions to Form a Palindrome