Common Dynamic Programming State Definitions: Patterns from the LeetCode Repository

Dynamic programming state definitions typically follow dimensional patterns like dp[i] for linear sequences, dp[i][j] for pairs or grids, dp[i][j][k] for triple parameters, and dp[i][mask] for subset problems, each capturing essential sub-problem information to enable optimal substructure.

Dynamic programming (DP) solves complex problems by decomposing them into overlapping sub-problems and caching their solutions. The foundation of any DP solution lies in its state definition—the mathematical representation of a sub-problem at a specific stage of the computation. This article examines the canonical state patterns documented in the azl397985856/leetcode repository, specifically within thinkings/dynamic-programming.en.md, and illustrates how these definitions translate into efficient code implementations.

One-Dimensional State Definitions (dp[i])

The simplest and most common DP state uses a single dimension to represent the solution after processing the first i elements. According to the repository's analysis in lines 42‑45 of thinkings/dynamic-programming.en.md, this pattern frequently appears when analyzing a single string or sequence, where dp[i] denotes the optimal value for the prefix ending at index i.

This definition exhibits optimal substructure: the value of dp[i] depends only on previously computed states like dp[i-1] or dp[i-2]. Once calculated, the state never changes, satisfying the no‑aftereffect property required for memoization.

Example: Climbing Stairs

The classic "Climbing Stairs" problem illustrates the dp[i] pattern, where dp[i] represents the number of distinct ways to reach step i.

def climbStairs(n: int) -> int:
    # dp[i] = ways to reach step i

    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]      # transition

    return dp[n]

Two-Dimensional State Definitions (dp[i][j])

When a problem requires tracking two independent parameters—such as two indices in a pair of strings or coordinates on a grid—a two-dimensional state becomes necessary. The repository notes in lines 49‑52 of thinkings/dynamic-programming.en.md that dp[i][j] typically represents the state involving two strings, where i and j index into the first and second string respectively.

This pattern also applies to grid-based DP (where i and j represent row and column coordinates) and interval DP (where i and j denote the left and right boundaries of a substring). The repository specifically references the grid application in lines 363‑376 when discussing problem 62 (Unique Paths), and the interval application in lines 91‑94 for palindrome-related problems.

Example: Unique Paths on a Grid

For an m×n grid, dp[i][j] stores the number of ways to reach cell (i, j), demonstrating the Cartesian product of parameters mentioned in the repository's complexity analysis.

def uniquePaths(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 or j == 0:
                dp[i][j] = 1               # boundary condition

            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]   # transition

    return dp[m-1][n-1]

Example: Longest Palindromic Subsequence (Interval DP)

Interval DP uses dp[i][j] to represent the optimal solution for the substring spanning indices i to j. This aligns with the repository's explanation in lines 91‑94 of thinkings/dynamic-programming.en.md regarding palindrome problems.

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1                       # one-letter palindrome

    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

Three-Dimensional State Definitions (dp[i][j][k])

Some problems require tracking three independent parameters, such as two string indices plus an additional flag or constraint. The repository identifies this pattern in lines 68‑70 of thinkings/dynamic-programming.en.md, noting that dp[i][j][k] becomes necessary when a third dimension encodes extra state information beyond the two primary indices.

Adding a third dimension increases both time and space complexity to $O(i \cdot j \cdot k)$, so this pattern is reserved for problems where the additional parameter is essential to the problem constraints, such as edit distance variants with special operation rules or string matching with wildcard states.

Example: Edit Distance with Additional State Flag

The following implementation demonstrates a three-dimensional DP where k represents an additional binary flag (e.g., whether a specific operation has been used), illustrating the pattern described in the repository's analysis.

def minDistance(s: str, t: str) -> int:
    m, n = len(s), len(t)
    INF = 10**9
    dp = [[[INF] * 2 for _ in range(n+1)] for _ in range(m+1)]
    dp[0][0][0] = dp[0][0][1] = 0
    for i in range(m+1):
        for j in range(n+1):
            for k in range(2):
                cur = dp[i][j][k]
                if i < m:
                    dp[i+1][j][k] = min(dp[i+1][j][k], cur + 1)   # delete

                if j < n:
                    dp[i][j+1][k] = min(dp[i][j+1][k], cur + 1)   # insert

                if i < m and j < n:
                    cost = 0 if s[i]==t[j] else 1
                    dp[i+1][j+1][k] = min(dp[i+1][j+1][k], cur + cost)  # replace / match

    return min(dp[m][n])

Bitmask State Definitions (dp[i][mask])

For problems involving subsets or combinations—such as the Traveling Salesman Problem (TSP)—the state often combines an index with a bitmask representing which items have been visited. The repository highlights this pattern in lines 70‑71 of thinkings/dynamic-programming.en.md, explaining that mask encodes a subset of items using bit flags, enabling $O(2^n \cdot n)$ solutions for otherwise exponential problems.

This definition leverages the Cartesian product of the index dimension and the subset space, where the total state count equals $n \cdot 2^n$. The bitmask efficiently tracks visited states without requiring an additional dimension for each item, making it essential for permutation and subset optimization problems.

Example: Traveling Salesman Problem

The following implementation demonstrates dp[i][mask], where i is the current city and mask represents the set of visited cities, directly reflecting the repository's explanation.

def tsp(dist):
    n = len(dist)
    INF = 10**9
    dp = [[INF] * (1 << n) for _ in range(n)]
    dp[0][1] = 0                     # start at city 0, visited only {0}

    for mask in range(1, 1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                nxt = mask | (1 << v)
                dp[v][nxt] = min(dp[v][nxt], dp[u][mask] + dist[u][v])
    full = (1 << n) - 1
    return min(dp[u][full] + dist[u][0] for u in range(1, n))

Key Files in the Repository

The azl397985856/leetcode repository contains several reference implementations that demonstrate these state definitions in practice.

File	Why it matters for DP state definitions
thinkings/dynamic‑programming.en.md	Core explanatory document that lists the canonical state patterns (dp[i], dp[i][j], dp[i][j][k], dp[i][mask]) and discusses their complexity implications.
problems/62.unique‑paths.md	Concrete problem that uses the 2‑D grid state dp[i][j].
problems/63.unique‑paths‑ii.md	Extends the grid DP with obstacles, reinforcing the same state definition.
problems/53.maximum‑sum‑subarray-cn.en.md	Shows a 1‑D DP (dp[i] for maximum subarray ending at i).
problems/198.house‑robber.en.md	Another classic 1‑D DP (dp[i] = max loot up to house i).

Summary

• One-dimensional states (dp[i]) capture solutions for prefixes of a single sequence, as noted in lines 42‑45 of thinkings/dynamic-programming.en.md, and work best for linear problems like climbing stairs or house robber.
• Two-dimensional states (dp[i][j]) handle pairs of indices for grid traversal, string matching, or interval subproblems, referenced in lines 49‑52 and lines 91‑94 for grid and palindrome examples respectively.
• Three-dimensional states (dp[i][j][k]) add a third parameter for complex constraints, documented in lines 68‑70, increasing complexity to $O(i \cdot j \cdot k)$ but enabling solutions for problems with additional flags.
• Bitmask states (dp[i][mask]) encode subsets using bit flags for permutation and traveling salesman problems, explained in lines 70‑71, achieving $O(n \cdot 2^n)$ complexity for subset optimization.

Frequently Asked Questions

What is a state in dynamic programming?

A state in dynamic programming is a mathematical representation that captures all essential information about a sub-problem at a specific stage of the computation. According to the azl397985856/leetcode repository, the state definition determines the dimensionality of the DP table and directly influences the algorithm's time and space complexity. For example, dp[i] stores the solution for the first i elements, while dp[i][j] tracks solutions involving two indices.

How do I choose between 1D and 2D DP state definitions?

Choose a one-dimensional state when the problem depends only on a single sequence or position, such as computing the maximum sum subarray ending at index i (as seen in problems/53.maximum-sum-subarray-cn.en.md). Opt for a two-dimensional state when the problem involves pairs of indices, such as comparing two strings, traversing a grid, or solving interval subproblems like the longest palindromic subsequence (referenced in lines 91‑94 of thinkings/dynamic-programming.en.md). The repository emphasizes that the Cartesian product of parameter ranges determines the total state count.

When should I use bitmask DP states?

Use bitmask state definitions (dp[i][mask]) when the problem requires tracking which items have been visited or selected from a set, particularly in permutation or subset optimization problems like the Traveling Salesman Problem. As documented in lines 70‑71 of thinkings/dynamic-programming.en.md, the mask parameter encodes a subset using bit flags, enabling solutions with $O(n \cdot 2^n)$ complexity instead of factorial time. This pattern is essential when the state space involves combinations rather than just linear sequences.

What are the complexity implications of adding dimensions to DP states?

Each additional dimension multiplies the total number of states by the range of that parameter, directly increasing both time and space complexity according to the Cartesian product principle noted in lines 53‑57 of thinkings/dynamic-programming.en.md. For example, moving from dp[i] (1D) to dp[i][j] (2D) increases complexity from $O(n)$ to $O(n^2)$, while dp[i][j][k] (3D) results in $O(n^3)$ complexity. The repository advises selecting the minimal state representation that captures all necessary problem constraints to optimize performance.

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