How to Identify and Solve Dynamic Programming Problems: A Systematic Guide

Dynamic programming problems exhibit optimal substructure and overlapping subproblems, and can be solved systematically by defining states, deriving transition equations, and iterating bottom-up or top-down with memoization.

The azl397985856/leetcode repository provides a comprehensive framework for mastering these techniques through its detailed notes on algorithmic patterns. According to thinkings/dynamic-programming.md, successful DP problem-solving requires recognizing specific mathematical properties and following a structured workflow from state definition to space optimization.

Recognizing Dynamic Programming Problems

Before implementing a solution, you must identify whether a problem warrants dynamic programming. Two mathematical properties distinguish DP candidates from general recursive problems.

Optimal Substructure

A problem has optimal substructure when the optimum solution can be constructed from optimal solutions of smaller sub-instances. Look for problem descriptions that suggest recursive relationships, such as "the best way to reach step i depends on the best ways to reach previous steps." This property appears in optimization problems where local optimal choices contribute to the global optimum.

Overlapping Subproblems

Overlapping subproblems occur when the same sub-problem is solved multiple times in a naive recursive solution. Signs include exponential recursion trees or repeated state calculations across different branches of the recursion. If a divide-and-conquer approach recalculates identical states repeatedly, your problem likely requires memoization or tabulation.

The Dynamic Programming Workflow

The thinkings/dynamic-programming.md file outlines a six-step methodology for solving DP problems once you have identified the appropriate pattern.

Define the State

Choose a concise representation that captures all necessary information for future decisions. Common state patterns include:

• Index-based state: dp[i] represents the best result up to position i (sequence problems)
• Two-dimensional state: dp[i][j] tracks results using the first i items with capacity j (knapsack variants)
• Bitmask state: dp[mask] encodes results for specific subsets of elements (traveling salesman, set cover)

Derive the Transition Equation

Express the current state in terms of previously computed states. This recurrence relation forms the mathematical core of your solution. For example, the classic 0/1 knapsack transition defined in the repository follows this pattern:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

The transition mirrors the logic of recursive decision-making: either you exclude the current item (carrying forward dp[i-1][w]) or include it (adding value to the remaining capacity).

Choose Your Iteration Strategy

Bottom-up tabulation fills a table iteratively following the dependency direction, avoiding recursion overhead and function call stack limits. This approach works best when the state space is dense and most subproblems need computation.

Top-down memoization maintains a cache of computed states and recurses only when encountering uncomputed values. Use this strategy when the state space is sparse or when you cannot easily determine the iteration order.

Handle Initialization and Edge Cases

Initialize the DP table with base values that represent trivial subproblems, such as dp[0] = 0 for an empty prefix or dp[0][j] = 0 for zero items. Carefully validate boundary conditions involving negative numbers, zero capacity, or empty input arrays to prevent out-of-bounds errors or incorrect base cases.

Space Optimization Techniques

Many DP implementations reduce complexity from O(n·m) to O(m) by reusing a single array when the transition depends only on the previous row. The repository emphasizes this optimization in its space-optimization tips, particularly for knapsack and grid traversal problems.

Practical Implementation Examples

The azl397985856/leetcode repository provides concrete Go implementations demonstrating these concepts across different difficulty levels.

Fibonacci Numbers (Bottom-Up Tabulation)

This example demonstrates basic state definition and forward iteration using a one-dimensional array:

// dp[i] stores Fibonacci(i)
func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

0/1 Knapsack (Space-Optimized)

This implementation reduces the two-dimensional state to a single array by iterating backwards through capacities, preventing overwrite of values still needed for the current computation:

func knapsack(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    for i := 0; i < len(weights); i++ {
        w, v := weights[i], values[i]
        for c := capacity; c >= w; c-- { // reverse to reuse current row
            if dp[c] < dp[c-w]+v {
                dp[c] = dp[c-w] + v
            }
        }
    }
    return dp[capacity]
}

Longest Increasing Subsequence (Advanced DP)

This solution combines dynamic programming with binary search to achieve O(n log n) complexity, demonstrating how state definition can evolve beyond simple arrays:

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        // binary search for insertion point
        i, j := 0, len(tails)
        for i < j {
            m := (i + j) / 2
            if tails[m] < x {
                i = m + 1
            } else {
                j = m
            }
        }
        if i == len(tails) {
            tails = append(tails, x)
        } else {
            tails[i] = x
        }
    }
    return len(tails)
}

Summary

• Identify DP candidates by verifying optimal substructure and overlapping subproblems in the problem constraints
• Define concise state representations (dp[i], dp[i][j], or dp[mask]) that capture all necessary decision context
• Formulate transition equations that express current states in terms of previously computed values
• Prefer bottom-up tabulation for dense state spaces and top-down memoization when the state space is sparse
• Optimize space complexity by reusing arrays when transitions depend only on previous rows, as demonstrated in thinkings/dynamic-programming.md

Frequently Asked Questions

What is the difference between top-down and bottom-up dynamic programming?

Top-down dynamic programming uses recursion with memoization, computing states only when needed and storing results to avoid redundant calculations. Bottom-up dynamic programming uses iterative tabulation, filling a table from base cases upward without recursion overhead. According to the repository, bottom-up is generally preferred for LeetCode problems due to better constant factors and no recursion depth limits.

How do I know if a problem has overlapping subproblems?

You can identify overlapping subproblems by drawing the recursion tree for small inputs. If the same parameters appear multiple times in different branches, or if a naive recursive solution exhibits exponential time complexity due to repeated calculations, the problem has overlapping subproblems. The thinkings/dynamic-programming.md note suggests looking for "exponential recursion trees or repeated state calculations" as primary indicators.

When should I use greedy algorithms instead of dynamic programming?

Use greedy algorithms when the problem lacks overlapping subproblems and exhibits the greedy choice property, where local optimal choices lead to a global optimum without reconsideration. Consult thinkings/greedy.md in the repository for problems where greedy approaches suffice. Dynamic programming is necessary when subproblems overlap and you must compare multiple candidate solutions to find the optimum.

Can space optimization change the time complexity of a DP solution?

No, space optimization techniques such as reusing a single array instead of a full table reduce memory usage from O(n·m) to O(m) or O(n) but do not alter the time complexity. The number of state transitions remains identical; only the storage mechanism changes. The repository implements this pattern in the 0/1 knapsack example by iterating backwards through capacities to preserve the previous row's values in-place.

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