Concept Architecture
Concept
Theoretically, Dynamic Programming is a mathematical optimisation method for solving complex sequential decision problems by decomposing them into overlapping subproblems that satisfy the principle of optimality. Developed by Richard Bellman, the method is founded on recursive optimisation and optimal control theory. Dynamic programming exists to efficiently solve multistage decision problems by storing intermediate solutions and avoiding repeated computation, making it fundamental to health economic decision modelling.
Mathematically, dynamic programming represents a problem through recursive value functions governed by Bellman's Principle of Optimality. The optimal solution at each stage depends only on the current state and the optimal solutions to subsequent stages. The method typically involves recursive functional equations that are solved either forwards or backwards through the state space to determine the optimal policy.
In practice, dynamic programming is implemented in optimisation software and numerical algorithms for sequential decision-making problems. In health economics, it underpins treatment sequencing, resource allocation, optimal screening policies, stochastic control problems and certain Markov decision process models. It is also used in computational optimisation where exhaustive enumeration would be computationally infeasible.
Purpose
Used to determine optimal solutions for multistage decision problems by recursively solving overlapping subproblems, supporting sequential decision-making and optimisation in health economic modelling.
Mathematical Formulae
Primary Formula
V(s) = max? { R(s,a) + ?V(s?) }
Supporting Formulae
Bellman equation:
V*(s) = max? { R(s,a) + ??P(s?|s,a)V*(s?) }
Bellman expectation equation:
V(s) = R(s) + ??P(s?|s)V(s?)
Recursive optimisation:
f(n) = min { g?(n), g?(n), ?, g?(n) }
Related Mathematical Methods
- Bellman Equation
- Markov Decision Process
- Stochastic Dynamic Programming
- Backward Induction
- Value Iteration
- Policy Iteration
- Optimal Control
Example
A health authority must determine the optimal sequence of treatments for patients with chronic disease over five annual decision periods.
At each year, the decision is whether to continue the current treatment or switch to an alternative.
Dynamic programming evaluates the expected future costs and health outcomes for every possible state and recursively determines the treatment choice that maximises lifetime net health benefit.
The resulting policy identifies the optimal treatment at every disease stage while accounting for future consequences of current decisions.
Excel Implementation
| Function | Example Formula | Health Economics Application |
|---|---|---|
| MAX | =MAX(Value1,Value2,Value3) | Selects the optimal value at each decision stage. |
| INDEX | =INDEX(ValueTable,State,Decision) | Retrieves value functions for individual states. |
| MATCH | =MATCH(CurrentState,StateRange,0) | Identifies the current state within the optimisation table. |
| IF | =IF(ValueA>ValueB,ValueA,ValueB) | Chooses the optimal decision recursively. |
| Solver Add-in | Optimise objective across decision variables | Solves dynamic optimisation problems when implemented in spreadsheets. |
VBA (Optional)
VBA can automate recursive Bellman updates, perform backward induction and identify optimal policies across large state-transition models.
Sources
- Bellman RE. Dynamic Programming.
- Bertsekas DP. Dynamic Programming and Optimal Control.
- Puterman ML. Markov Decision Processes: Discrete Stochastic Dynamic Programming.
- Briggs A, Claxton K, Sculpher M. Decision Modelling for Health Economic Evaluation.
- Drummond MF, Sculpher MJ, Claxton K, Stoddart GL, Torrance GW. Methods for the Economic Evaluation of Health Care Programmes.
- Powell WB. Approximate Dynamic Programming: Solving the Curses of Dimensionality.
Related Concepts (2)
Library
Publications
3
Computer Science Distilled — Wladston Ferreira Filho, 1st Edition ed., 2017 (Code Energy)
A compact overview of foundational computer science, connecting algorithms, data structures, complexity, recursion, graphs and core computational ideas.
BookView source →Grokking Algorithms — Aditya Y. Bhargava, 1st Edition ed., 2016 (Manning Publications)
An illustrated introduction to practical algorithms, including binary search, sorting, recursion, hash tables, graph search and dynamic programming.
BookView source →A Common-Sense Guide to Data Structures and Algorithms — Jay Wengrow, 2nd Edition ed., 2020 (The Pragmatic Bookshelf)
A practical guide to data structures and algorithm efficiency, covering arrays, hashes, stacks, queues, trees, graphs, heaps, recursion and dynamic programming.
BookView source →
Frequently Asked Questions (6)
What is dynamic programming?
An algorithmic technique that solves a problem by combining solutions to overlapping subproblems and storing those solutions to avoid repeated computation.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
How does dynamic programming solve a problem?
Dynamic programming solves a problem by combining solutions to overlapping subproblems and storing those solutions to avoid repeated computation. Rather than recomputing the answer to a subproblem each time it recurs, dynamic programming records it once and reuses it. This combination of solving subproblems and storing their results is what defines dynamic programming By recording each subproblem's answer the first time it is found, the technique trades a little memory for a large saving in computation wherever the same subproblems recur.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
Why does dynamic programming store subproblem solutions?
Dynamic programming stores subproblem solutions to avoid repeated computation, since its subproblems overlap and would otherwise be solved many times over. By keeping each solution once it is found, dynamic programming reuses it whenever the same subproblem arises again. This storage is central to the technique, because it is what turns a potentially wasteful recomputation into an efficient reuse of results By recording each subproblem's answer the first time it is found, the technique trades a little memory for a large saving in computation wherever the same subproblems recur.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
What kind of subproblems does dynamic programming exploit?
Dynamic programming exploits overlapping subproblems, meaning subproblems that recur within the larger problem so that their solutions can be reused. Because it combines solutions to these overlapping subproblems and stores them, the same result serves in many places. This reliance on overlap distinguishes dynamic programming from techniques whose subproblems are solved independently and do not recur By recording each subproblem's answer the first time it is found, the technique trades a little memory for a large saving in computation wherever the same subproblems recur.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
What does dynamic programming avoid by storing solutions?
By storing solutions, dynamic programming avoids repeated computation of the same overlapping subproblems. Without storage, each recurrence of a subproblem would be solved afresh, wasting effort; with it, the stored answer is reused. Avoiding this repeated work is the efficiency that storing solutions to overlapping subproblems gives dynamic programming By recording each subproblem's answer the first time it is found, the technique trades a little memory for a large saving in computation wherever the same subproblems recur.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
How does dynamic programming relate to divide and conquer?
Dynamic programming combines solutions to overlapping subproblems and stores them to avoid repeated computation, while divide and conquer divides a problem into smaller instances, solves them, often recursively, and combines their solutions. Both break a problem into parts, but dynamic programming stores results because its subproblems overlap, whereas divide and conquer generally works on instances that do not recur, so it has no need to store them By recording each subproblem's answer the first time it is found, the technique trades a little memory for a large saving in computation wherever the same subproblems recur.
Source: Algorithms and Theory of Computation Handbook (1999/2022). “Dynamic programming.” NIST Dictionary of Algorithms and Data Structures.
Trust Record
Verified by Dr Darrin Baines
British health economist
Professional identity: darrinbaines.org
Verification date: 2 Apr 2026
Content version: 1.0.0
Canonical Identity
- Persistent URI
- https://healtheconomics.wiki/concept/dynamic-programming
- Term code
- CS-SC-AL-004
Stable URI · Machine-readable · Resolvable · CC BY 4.0