Example usage

In the previous article, we delved deeply into the fundamentals of network flow algorithms and learned how to solve complex problems by modeling them as networks. Today, we shift our focus to another critical algorithmic paradigm: Dynamic Programming (DP)—and explore practical applications of the dynamic programming mindset.

Dynamic programming is an algorithm design paradigm used to solve optimization problems efficiently by breaking them down into smaller subproblems and avoiding redundant computation. In this article, we emphasize how to apply the core principles of dynamic programming to tackle complex problems—not just textbook DP problems in isolation.

Core Principles of Dynamic Programming

The essence of dynamic programming lies in two key properties:

• Optimal Substructure: An optimal solution to the overall problem can be constructed from optimal solutions to its subproblems.
• Overlapping Subproblems: The same subproblem is solved multiple times in a naive recursive approach—hence caching intermediate results yields significant efficiency gains.

Practical application of DP typically follows these four steps:

1. Define the State: Clearly specify what information each state represents—the minimal description needed to capture the problem’s progress.
2. State Transition: Establish recurrence relations that express how to compute the current state using previously computed states (i.e., how solutions to subproblems combine into a solution for the larger problem).
3. Base Cases: Identify the simplest subproblems whose solutions are known or trivial—these anchor the recurrence.
4. Optimization Strategy: Use either memoization (top-down recursion with caching) or tabulation (bottom-up iterative filling of a table) to store and reuse intermediate results.

Application Examples

Below are several classic examples illustrating how the dynamic programming mindset manifests in real-world problem solving.

Example 1: The 0–1 Knapsack Problem

Problem Statement: Given a set of items, each with a weight and a value, select a subset of items such that their total weight does not exceed a given capacity, while maximizing total value.

State Definition:
Let dp[i][j] denote the maximum value achievable using the first i items with a knapsack capacity of j.

State Transition:
For item i (0-indexed in input arrays, so i−1 in code):

• If item i is not included: dp[i][j] = dp[i−1][j]
• If item i is included (only possible if j ≥ weights[i−1]): dp[i][j] = dp[i−1][j − weights[i−1]] + values[i−1]

Thus, the recurrence is:

Base Cases:

• dp[0][j] = 0 for all j: zero items yield zero value.
• dp[i][0] = 0 for all i: zero capacity allows no items.

Code Implementation:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]  # Skip item i
            else:
                dp[i][j] = max(
                    dp[i-1][j], 
                    dp[i-1][j - weights[i-1]] + values[i-1]
                )  # Include item i
                
    return dp[n][capacity]

# Example usage
weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 6
print(knapsack(weights, values, capacity))  # Output: 55

Example 2: Edit Distance (Levenshtein Distance)

Problem Statement: Given two strings word1 and word2, compute the minimum number of single-character edit operations (insertion, deletion, or substitution) required to transform word1 into word2.

State Definition:
Let dp[i][j] represent the minimum edit distance between the first i characters of word1 and the first j characters of word2.

State Transition:
Three operations lead to dp[i][j]:

• Insertion: Add word2[j−1] → cost dp[i][j−1] + 1
• Deletion: Remove word1[i−1] → cost dp[i−1][j] + 1
• Substitution/Match: Replace word1[i−1] with word2[j−1], or do nothing if they match → cost dp[i−1][j−1] + (0 if equal else 1)

So the recurrence is:

Base Cases:

• dp[0][j] = j: Convert empty string to word2[:j] requires j insertions.
• dp[i][0] = i: Convert word1[:i] to empty string requires i deletions.

Code Implementation:

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j  # Insert j chars
            elif j == 0:
                dp[i][j] = i  # Delete i chars
            else:
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]  # No operation needed
                else:
                    dp[i][j] = 1 + min(
                        dp[i-1][j],    # delete
                        dp[i][j-1],    # insert
                        dp[i-1][j-1]   # substitute
                    )
                
    return dp[m][n]

# Example usage
word1 = "horse"
word2 = "ros"
print(min_distance(word1, word2))  # Output: 3

Summary

In this article, we examined the foundational ideas behind dynamic programming and demonstrated their application through two canonical problems—the 0–1 Knapsack Problem and Edit Distance. Dynamic programming is far more than a computational technique; it is a way of thinking: a disciplined method for decomposing complexity, recognizing structural patterns, and building solutions incrementally from well-defined substructures.

In the next article, we will dive deeper into classical DP problem patterns—such as longest common subsequence, coin change, and matrix chain multiplication—and explore advanced strategies for tackling challenging variants and optimizations.

We hope you’ll continue following this tutorial series to strengthen your algorithmic intuition and problem-solving skills.