Dynamic programming
Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
Algorithms Every Programmer Should Know
An algorithm-design technique that solves overlapping subproblems and stores intermediate results to avoid repeated computation.
- How it is used
- Uses stored smaller answers to choose maximum value under a 0/1 capacity constraint and to compute all-pairs shortest paths.
- How deep it goes
- Works through table initialization, include-or-skip transitions, a completed knapsack result, and complexity; also sketches distance-matrix updates.
- Examples
- Traces four cloud instances across capacities up to eight and tests intermediate vertices in a four-node graph.
- What you can do after
- Build it from scratch as a 2D 0/1 knapsack table and evaluate its time and memory costs.
Read how Algorithms Every Programmer Should Know explains dynamic programming →
Timeless Algorithms, The Foundational Ideas
Dynamic programming is an algorithmic technique that solves problems by decomposing them into related subproblems and combining their solutions, often reusing computed results.
- How it is used
- Structures multi-stage decisions and counting problems as related subproblems whose results can be reused.
- How deep it goes
- Develops structural conditions, state design, recurrences, base cases, memoization, and tabulation, including the computational cost of additional state dimensions.
- Examples
- Uses Fibonacci recursion, knapsack, coin change, inventory planning, and least-cost routing to illustrate different formulations.
- What you can do after
- Apply it by defining states, transitions, recurrences, and base cases, then evaluating subproblems through memoization or tabulation.
Read how Timeless Algorithms, The Foundational Ideas explains dynamic programming →
Build a Robo-Advisor with Python (From Scratch)
Dynamic programming is a computational technique that solves sequential decision problems by decomposing them into states, actions, transition probabilities, and recursively computed value functions.
- How it is used
- Optimizes multiperiod asset-allocation and spending decisions under uncertain wealth transitions.
- How deep it goes
- Works through discrete grids, normal-return transition probabilities, terminal values, expected-value maximization, and consumption-utility extensions.
- Examples
- Uses a $2 million wealth goal, stock-bond allocations, a 10-period wealth grid, and discrete consumption rates.
- What you can do after
- Build it from scratch for discrete wealth states, asset allocations, terminal goals, and consumption choices.
Read how Build a Robo-Advisor with Python (From Scratch) explains dynamic programming →
Grokking Algorithms, Second Edition
Dynamic programming is an algorithmic technique that solves overlapping subproblems by storing and reusing their results.
- How it is used
- Optimizes a choice under a constraint by building an answer from smaller problems.
- How deep it goes
- Walks through grid cells and grid-design questions, but gives no single formula for all solutions.
- Examples
- Uses item values in a knapsack, a timed travel itinerary, and a misspelled-word comparison.
- What you can do after
- Build it from scratch by choosing grid axes, filling smaller problems, and using their answers to find a maximum.
Read how Grokking Algorithms, Second Edition explains dynamic programming →
Applied Reinforcement Learning
Dynamic programming is an algorithmic technique that solves sequential decision or optimization problems by decomposing them into overlapping subproblems and combining their solutions.
- How it is used
- Plans for an MDP by using known transition probabilities and rewards to compute behavior.
- How deep it goes
- Explains value and policy iteration, then identifies state-space growth and complete-model requirements as practical limits.
- Examples
- Uses resource allocation to illustrate state-space growth, comparing 1,053 states with nearly six million.
- What you can do after
- Understand how known environment dynamics support planning and why state-space size can limit practical use.
Read how Applied Reinforcement Learning explains dynamic programming →
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
Dynamic programming is an algorithmic technique that solves a problem by combining solutions to overlapping smaller subproblems, typically storing intermediate results.
- How it is used
- Optimizes finite-resource allocations by solving smaller capacity-and-item cases and building a larger solution.
- How deep it goes
- Explains table construction, include-or-skip choices, and backward reconstruction of the selected items.
- Examples
- Uses a three-item knapsack table, a 75-pound item set, and athletic-budget allocation as concrete examples.
- What you can do after
- Builds a table-driven 0/1 knapsack solver and reconstructs the selected items.
Machine Learning Algorithms in Depth
Dynamic programming solves problems with overlapping subproblems by storing and reusing solutions to smaller subproblems.
- How it is used
- Organizes solutions to overlapping-subproblem algorithms, including tabular reinforcement-learning solutions to Bellman equations.
- How deep it goes
- Derives states, transitions, base cases, traversal strategies, complexity, and implementations, stopping short of broader algorithmic applications.
- Examples
- Uses binomial coefficients, the C(5,2) recursion tree, Python table implementations, and tabular reinforcement-learning value computation.
- What you can do after
- Build it from scratch by designing DP states, transitions, base cases, memoized recursion, and bottom-up tables.
Read how Machine Learning Algorithms in Depth explains dynamic programming →
Advanced Algorithms and Data Structures
Dynamic programming is an algorithmic technique that solves overlapping subproblems once, stores their results, and combines them to solve the original problem.
- How it is used
- Applies stored subproblem results to optimization problems such as 0-1 knapsack.
- How deep it goes
- Defines the recursive decomposition and storage strategy but stops short of implementation details.
- Examples
- Uses a 1000-kilogram crate and 62 candidate items to contrast dynamic programming with exhaustive combination search.
- What you can do after
- Evaluate when repeated subproblems justify stored solutions and when capacity-dependent performance is acceptable.
Read how Advanced Algorithms and Data Structures explains dynamic programming →
What to know first
- Bellman equationA Bellman equation recursively relates a state or action value to an immediate reward and the expected discounted value of successor states or actions.
- brute-force searchBrute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
- machine learningMachine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.
- optimizationOptimization is the systematic selection or modification of values, configurations, or implementations to improve a defined objective, often subject to constraints.
Related concepts
- Bellman equationuses · A Bellman equation recursively relates a state or action value to an immediate reward and the expected discounted value of successor states or actions.
- memoizationuses · Memoization is an optimization technique that stores results of computations with their inputs so later evaluations with equivalent inputs can reuse them without recomputation.
- Floyd–Warshallused by · Floyd–Warshall is a dynamic programming algorithm for computing shortest-path distances between every pair of vertices in a weighted graph.
- linear programmingcontrasts with · Linear programming is an optimization method that maximizes or minimizes a linear objective subject to linear equality or inequality constraints.
- global optimumproduces · A global optimum is a feasible point or solution whose objective value is at least as favorable as that of every other point or solution in the domain.
Questions about dynamic programming
What is dynamic programming?
Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
Which Manning books explain dynamic programming?
Algorithms Every Programmer Should Know, Timeless Algorithms, The Foundational Ideas, Build a Robo-Advisor with Python (From Scratch), Grokking Algorithms, Second Edition, Applied Reinforcement Learning, Classic Computer Science Problems in Swift: Essential techniques for practicing programmers, Machine Learning Algorithms in Depth and Advanced Algorithms and Data Structures.
What should I know before learning dynamic programming?
Manning books that teach dynamic programming usually introduce Bellman equation, brute-force search, machine learning and optimization first.
What is the difference between dynamic programming and linear programming?
Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions. Linear programming is an optimization method that maximizes or minimizes a linear objective subject to linear equality or inequality constraints.
What is dynamic programming also called?
Dynamic programming is also called DP.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.







