Chapter 13. Dynamic Programming

Chapter 13: Dynamic Programming. 25 sections.

25 items

Chapter 13. Dynamic Programming

Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.1 DP State Design

State design is the most important step in dynamic programming.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.2 Recurrence Relations

After defining a state, the next step is to determine how one state depends on other states.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.3 Memoization

Once a state and recurrence have been defined, the most direct way to implement a dynamic programming solution is memoization.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.4 Tabulation

Memoization evaluates states on demand through recursion.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.5 One-Dimensional Dynamic Programming

One-dimensional dynamic programming is the simplest and most common form of dynamic programming.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.6 Two-Dimensional Dynamic Programming

One-dimensional dynamic programming models progress along a single axis.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.7 Knapsack

The knapsack problem occupies a special place in dynamic programming.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.8 Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is one of the most influential dynamic programming problems ever studied.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.9 Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is one of the most important sequence optimization problems in algorithm design.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.10 Edit Distance

The edit distance problem asks a deceptively simple question: > How different are two strings?
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.11 Interval Dynamic Programming

Most dynamic programming problems decompose a problem into prefixes, suffixes, positions, or capacities.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.12 Tree Dynamic Programming

Many dynamic programming problems are defined on linear structures such as arrays, strings, and intervals.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.13 Bitmask Dynamic Programming

Most dynamic programming problems use states based on positions, intervals, capacities, or tree nodes.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.14 Probability Dynamic Programming

Probability dynamic programming appears when each transition has uncertainty.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.15 Counting Dynamic Programming

Many dynamic programming problems ask for the best solution: ```text minimum cost maximum value
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.16 Optimization Dynamic Programming

Optimization dynamic programming is the form most programmers first associate with DP.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.17 Convex Hull Trick

Many dynamic programming solutions are correct but too slow.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.18 Divide-and-Conquer Dynamic Programming

Many dynamic programming recurrences have the correct state design but suffer from an expensive transition step.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.19 Knuth Optimization

Knuth optimization is a specialized dynamic programming optimization for interval-like recurrences.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.20 Dynamic Programming Design Patterns and Problem-Solving Framework

Throughout this chapter, we have studied many different forms of dynamic programming: * one-dimensional DP * two-dimensional DP * knapsack DP
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.21 Dynamic Programming on Graphs

Dynamic programming is easiest when subproblems form a simple order: left to right, bottom to top, short interval to long interval, child before parent.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.22 State Compression and Memory Optimization

One of the most common mistakes in dynamic programming is focusing exclusively on time complexity while ignoring memory consumption.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.23 Correctness Proofs for Dynamic Programming

A dynamic programming solution is easy to mistrust.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.24 Testing Dynamic Programming Algorithms

Dynamic programming algorithms are especially prone to subtle bugs.
algorithms dynamic-programming Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 13. Dynamic Programming ›

13.25 Case Studies

This chapter has treated dynamic programming as a toolkit: state design, recurrence construction, memoization, tabulation, counting, optimization, graph DP, interval DP, tree DP, bitmask DP, and trans...
algorithms dynamic-programming Jun 1, 2026