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

> Learn to identify and solve dynamic programming problems. Master states, transitions, and memoization with this systematic guide. Boost your problem-solving skills.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: how-to-guide
- Published: 2026-03-06

---

**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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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:

```go
// 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:

```go
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:

```go
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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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.