Dynamic programming
Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
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 →
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 →
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 computation results with their inputs so equivalent later evaluations can reuse them without recomputation.
- optimizationkind of · Optimization is the systematic selection or adjustment of values, actions, or system designs to improve a specified objective, often subject to constraints.
- linear programmingcontrasts with · Linear programming is an optimization method that maximizes or minimizes a linear objective subject to linear equality or inequality constraints.
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.