How to Apply Dynamic Programming to Solve Optimization Problems

Dynamic programming transforms exponential-time combinatorial optimization problems into polynomial-time solutions by caching optimal solutions to overlapping subproblems in a structured DP table.

Dynamic programming (DP) is a systematic method for solving complex optimization problems by breaking them into smaller, manageable subproblems. According to the labuladong/fucking-algorithm repository, mastering DP requires understanding two fundamental mathematical properties and following a rigorous framework to define states, derive transitions, and implement efficient computation orders. This guide explains how to apply dynamic programming to solve optimization problems using concrete implementations from the source code.

Core Concepts: Optimal Substructure and Overlapping Subproblems

Every DP solution relies on identifying two key properties in the target problem:

• Optimal substructure – The optimal solution to the main problem can be constructed from optimal solutions to its subproblems. For example, the maximum value for a knapsack of capacity W using N items depends on the maximum value for capacity W using N-1 items.

• Overlapping subproblems – A naive recursive approach would recompute the same subproblems exponentially many times. DP eliminates this redundancy by storing each subproblem's result in a cache or table.

As detailed in 动态规划系列/最优子结构.md, recognizing these properties allows you to define a DP state (e.g., dp[i][w]) that stores the optimal value for a specific sub-instance.

The Dynamic Programming Framework

Applying dynamic programming follows a four-step methodology consistently used throughout the labuladong/fucking-algorithm codebase.

Step 1: Define the DP State

Identify the variables that completely describe a subproblem. Common state variables include:

• Sequence indices (i, j) – representing prefixes of input arrays or strings.
• Resource constraints (w, c) – representing remaining capacity, budget, or time.

For the 0-1 knapsack problem implemented in 动态规划系列/背包问题.md, the state is defined as dp[i][w], representing the maximum value achievable using the first i items with a bag capacity of w.

Step 2: Derive the Transition Formula

Write the recurrence relation that computes a state based on previously solved states. The general pattern involves a choice: decide whether to include the current element or exclude it.

For the knapsack problem, the transition is:

dp[i][w] = max(
    dp[i-1][w],                     // skip item i
    dp[i-1][w - wt[i-1]] + val[i-1] // take item i
)

This pattern appears across optimization problems including longest common subsequence, edit distance, and minimum cost deletion, as documented in 动态规划系列/LCS.md.

Step 3: Establish Base Cases

Define the trivial solutions that anchor the recurrence. Typically:

• dp[0][*] = 0 – zero items yield zero value.
• dp[*][0] = 0 – zero capacity yields zero value.

These base cases are implicitly handled in Java by array initialization (defaulting to 0), but must be explicitly set in languages without default initialization.

Step 4: Determine Computation Order

Choose between top-down (memoization) and bottom-up (tabulation) approaches:

• Top-down: Start from the target state (dp[N][W]), recursively compute dependencies, and cache results. Useful when many states are unreachable.
• Bottom-up: Iteratively fill the DP table starting from base cases. Usually faster due to avoiding recursion overhead.

The article 动态规划系列/最优子结构.md explains how traversal direction (forward, backward, or diagonal) depends on the transition formula's dependencies.

Practical Implementation: 0-1 Knapsack Problem

The following Java implementation from 动态规划系列/背包问题.md demonstrates the complete framework:

// File: 动态规划系列/背包问题.md
int knapsack(int W, int N, int[] wt, int[] val) {
    // dp[i][w] = max value using first i items with capacity w
    int[][] dp = new int[N + 1][W + 1];
    
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                dp[i][w] = dp[i - 1][w];  // cannot take
            } else {
                dp[i][w] = Math.max(
                    dp[i - 1][w],                             // skip
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]    // take
                );
            }
        }
    }
    return dp[N][W];  // optimal value
}

Key observations:

• The state dp[i][w] stores the optimal substructure property.
• The transition implements the "take or skip" choice.
• Base cases are implicitly zero-initialized.

Memoization vs. Tabulation: Longest Common Subsequence Example

The 动态规划系列/LCS.md file illustrates the top-down memoization approach for finding the Longest Common Subsequence:

// File: 动态规划系列/LCS.md
class Solution {
    int[][] memo;  // -1 means uncomputed

    public int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dp(s1, 0, s2, 0);
    }

    int dp(String s1, int i, String s2, int j) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
        } else {
            memo[i][j] = Math.max(dp(s1, i + 1, s2, j),
                                 dp(s1, i, s2, j + 1));
        }
        return memo[i][j];
    }
}

Critical insight: Memoization eliminates the exponential recomputation inherent in naive recursion. The memo array caches results for states (i, j), converting the time complexity from $O(2^{m+n})$ to $O(m \times n)$.

Space Optimization Techniques

When the transition only depends on the previous row or column, you can reduce the DP table from 2D to 1D. The labuladong/fucking-algorithm repository demonstrates this in the knapsack context:

def knapsack(W, wt, val):
    N = len(wt)
    dp = [0] * (W + 1)               # 1-D space-optimized DP

    
    for i in range(N):
        # iterate weight backwards to reuse previous row values

        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
            
    return dp[W]

Why backward iteration matters: When using a 1D array, iterating w from high to low ensures that dp[w - wt[i]] still refers to the values from the previous item iteration (row i-1), not the current row. This maintains the 0-1 knapsack constraint where each item can only be used once.

Summary

• Optimal substructure and overlapping subproblems are the two mathematical properties that make dynamic programming applicable to optimization problems.
• The DP framework requires defining a state that captures subproblem parameters, deriving a transition formula that builds solutions from smaller states, establishing base cases, and choosing an appropriate computation order.
• Top-down memoization (caching recursive calls) and bottom-up tabulation (iterative table filling) are both valid approaches with different trade-offs in recursion depth and constant factors.
• Space optimization can reduce memory from $O(N \times W)$ to $O(W)$ or $O(N)$ when transitions only depend on previous rows, using careful iteration ordering.
• The labuladong/fucking-algorithm repository provides concrete implementations in 动态规划系列/背包问题.md and 动态规划系列/LCS.md that demonstrate these principles in production-ready code.

Frequently Asked Questions

What types of problems can be solved with dynamic programming?

Dynamic programming applies to optimization problems that exhibit optimal substructure (where the global optimum contains optimal solutions to subproblems) and overlapping subproblems (where the same subproblems recur many times). Common examples include the 0-1 knapsack problem, longest common subsequence, edit distance, and shortest path algorithms like Floyd-Warshall.

How do I know if a problem has optimal substructure?

A problem has optimal substructure if you can construct the optimal solution to the main problem by combining optimal solutions to its subproblems. To verify this, attempt to "cut" the problem at a decision point—such as choosing whether to include the last item in a knapsack—and check if the remaining subproblem must also be solved optimally for the overall solution to be optimal.

Should I use memoization or tabulation for dynamic programming?

Choose top-down memoization when many subproblems in the theoretical table are never actually reached, as it computes only necessary states and often mirrors the natural recursive problem structure. Choose bottom-up tabulation when you need to optimize constant factors or avoid recursion stack limits, as it eliminates function call overhead and typically offers better cache locality.

How can I reduce memory usage in dynamic programming solutions?

You can reduce space by observing that many DP transitions depend only on the previous row or column rather than the entire table. For example, in the 0-1 knapsack problem, you can compress the 2D dp[i][w] array into a 1D dp[w] array by iterating weights backwards from W down to wt[i], ensuring that dp[w - wt[i]] still references the previous iteration's values.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}