Skip to main content
Definition Website Computer and Technology

Dynamic Programming

Subject: Computer and Technology noun /daɪˈnæm.ɪk ˈproʊ.ɡræm.ɪŋ/ 1 definition

  1. Definition (noun)

    Entry #51 · Updated

    Dynamic Programming (DP) is an algorithmic design paradigm that solves complex optimization and counting problems by decomposing them into simpler, recurring subproblems and caching each subproblem's solution so it is computed only once. A problem is suited to DP when it exhibits two core properties: overlapping subproblems, where the same subproblems recur repeatedly during recursive decomposition, and optimal substructure, where an optimal global solution can be constructed from optimal solutions to its subproblems. Unlike standard divide-and-conquer algorithms that solve independent subproblems separately, DP trades memory space for execution speed by reusing stored intermediate results, typically reducing exponential naive recursion to polynomial or pseudo-polynomial time.

    Common Forms

    • Top-Down DP (Memoization): Evaluates the target problem recursively from the root and caches each subproblem's result in a lookup table or hash map so repeated calls return immediately.

    • Bottom-Up DP (Tabulation): Solves base cases first and iteratively populates an array or multi-dimensional table in dependency order until reaching the final state, eliminating recursion stack overhead.

    • Space-Optimized DP: Compresses a multi-dimensional DP table into a rolling one-dimensional array or a constant set of state variables whenever each transition depends only on a fixed window of prior states.

    • Bitmask DP: Encodes small subsets or visited-state configurations as integer bitmasks within the DP state key, making subset-based state spaces tractable for tasks such as Traveling Salesperson route optimization.

    Example

    A version-control tool computing the minimal line-by-line diff between two 1,000-line source files uses bottom-up dynamic programming to populate a Longest Common Subsequence (LCS) table across line-prefix pairs. Instead of re-evaluating shared suffixes across exponential recursive branches, each cell reuses adjacent prefix counts to identify the minimal set of insertions and deletions in 1,000 × 1,000 table operations.