StudySmarter - The all-in-one study app.

4.8 • +11k Ratings

More than 3 Million Downloads

Free

Suggested languages for you:

Americas

Europe

Dynamic Programming

- Calculus
- Absolute Maxima and Minima
- Absolute and Conditional Convergence
- Accumulation Function
- Accumulation Problems
- Algebraic Functions
- Alternating Series
- Antiderivatives
- Application of Derivatives
- Approximating Areas
- Arc Length of a Curve
- Area Between Two Curves
- Arithmetic Series
- Average Value of a Function
- Calculus of Parametric Curves
- Candidate Test
- Combining Differentiation Rules
- Combining Functions
- Continuity
- Continuity Over an Interval
- Convergence Tests
- Cost and Revenue
- Density and Center of Mass
- Derivative Functions
- Derivative of Exponential Function
- Derivative of Inverse Function
- Derivative of Logarithmic Functions
- Derivative of Trigonometric Functions
- Derivatives
- Derivatives and Continuity
- Derivatives and the Shape of a Graph
- Derivatives of Inverse Trigonometric Functions
- Derivatives of Polar Functions
- Derivatives of Sec, Csc and Cot
- Derivatives of Sin, Cos and Tan
- Determining Volumes by Slicing
- Direction Fields
- Disk Method
- Divergence Test
- Eliminating the Parameter
- Euler's Method
- Evaluating a Definite Integral
- Evaluation Theorem
- Exponential Functions
- Finding Limits
- Finding Limits of Specific Functions
- First Derivative Test
- Function Transformations
- General Solution of Differential Equation
- Geometric Series
- Growth Rate of Functions
- Higher-Order Derivatives
- Hydrostatic Pressure
- Hyperbolic Functions
- Implicit Differentiation Tangent Line
- Implicit Relations
- Improper Integrals
- Indefinite Integral
- Indeterminate Forms
- Initial Value Problem Differential Equations
- Integral Test
- Integrals of Exponential Functions
- Integrals of Motion
- Integrating Even and Odd Functions
- Integration Formula
- Integration Tables
- Integration Using Long Division
- Integration of Logarithmic Functions
- Integration using Inverse Trigonometric Functions
- Intermediate Value Theorem
- Inverse Trigonometric Functions
- Jump Discontinuity
- Lagrange Error Bound
- Limit Laws
- Limit of Vector Valued Function
- Limit of a Sequence
- Limits
- Limits at Infinity
- Limits at Infinity and Asymptotes
- Limits of a Function
- Linear Approximations and Differentials
- Linear Differential Equation
- Linear Functions
- Logarithmic Differentiation
- Logarithmic Functions
- Logistic Differential Equation
- Maclaurin Series
- Manipulating Functions
- Maxima and Minima
- Maxima and Minima Problems
- Mean Value Theorem for Integrals
- Models for Population Growth
- Motion Along a Line
- Motion in Space
- Natural Logarithmic Function
- Net Change Theorem
- Newton's Method
- Nonhomogeneous Differential Equation
- One-Sided Limits
- Optimization Problems
- P Series
- Particle Model Motion
- Particular Solutions to Differential Equations
- Polar Coordinates
- Polar Coordinates Functions
- Polar Curves
- Population Change
- Power Series
- Radius of Convergence
- Ratio Test
- Removable Discontinuity
- Riemann Sum
- Rolle's Theorem
- Root Test
- Second Derivative Test
- Separable Equations
- Separation of Variables
- Simpson's Rule
- Solid of Revolution
- Solutions to Differential Equations
- Surface Area of Revolution
- Symmetry of Functions
- Tangent Lines
- Taylor Polynomials
- Taylor Series
- Techniques of Integration
- The Fundamental Theorem of Calculus
- The Mean Value Theorem
- The Power Rule
- The Squeeze Theorem
- The Trapezoidal Rule
- Theorems of Continuity
- Trigonometric Substitution
- Vector Valued Function
- Vectors in Calculus
- Vectors in Space
- Washer Method
- Decision Maths
- Geometry
- 2 Dimensional Figures
- 3 Dimensional Vectors
- 3-Dimensional Figures
- Altitude
- Angles in Circles
- Arc Measures
- Area and Volume
- Area of Circles
- Area of Circular Sector
- Area of Parallelograms
- Area of Plane Figures
- Area of Rectangles
- Area of Regular Polygons
- Area of Rhombus
- Area of Trapezoid
- Area of a Kite
- Composition
- Congruence Transformations
- Congruent Triangles
- Convexity in Polygons
- Coordinate Systems
- Dilations
- Distance and Midpoints
- Equation of Circles
- Equilateral Triangles
- Figures
- Fundamentals of Geometry
- Geometric Inequalities
- Geometric Mean
- Geometric Probability
- Glide Reflections
- HL ASA and AAS
- Identity Map
- Inscribed Angles
- Isometry
- Isosceles Triangles
- Law of Cosines
- Law of Sines
- Linear Measure and Precision
- Median
- Parallel Lines Theorem
- Parallelograms
- Perpendicular Bisector
- Plane Geometry
- Polygons
- Projections
- Properties of Chords
- Proportionality Theorems
- Pythagoras Theorem
- Rectangle
- Reflection in Geometry
- Regular Polygon
- Rhombuses
- Right Triangles
- Rotations
- SSS and SAS
- Segment Length
- Similarity
- Similarity Transformations
- Special quadrilaterals
- Squares
- Surface Area of Cone
- Surface Area of Cylinder
- Surface Area of Prism
- Surface Area of Sphere
- Surface Area of a Solid
- Surface of Pyramids
- Symmetry
- Translations
- Trapezoids
- Triangle Inequalities
- Triangles
- Using Similar Polygons
- Vector Addition
- Vector Product
- Volume of Cone
- Volume of Cylinder
- Volume of Pyramid
- Volume of Solid
- Volume of Sphere
- Volume of prisms
- Mechanics Maths
- Acceleration and Time
- Acceleration and Velocity
- Angular Speed
- Assumptions
- Calculus Kinematics
- Coefficient of Friction
- Connected Particles
- Conservation of Mechanical Energy
- Constant Acceleration
- Constant Acceleration Equations
- Converting Units
- Elastic Strings and Springs
- Force as a Vector
- Kinematics
- Newton's First Law
- Newton's Law of Gravitation
- Newton's Second Law
- Newton's Third Law
- Power
- Projectiles
- Pulleys
- Resolving Forces
- Statics and Dynamics
- Tension in Strings
- Variable Acceleration
- Work Done by a Constant Force
- Probability and Statistics
- Bar Graphs
- Basic Probability
- Charts and Diagrams
- Conditional Probabilities
- Continuous and Discrete Data
- Frequency, Frequency Tables and Levels of Measurement
- Independent Events Probability
- Line Graphs
- Mean Median and Mode
- Mutually Exclusive Probabilities
- Probability Rules
- Probability of Combined Events
- Quartiles and Interquartile Range
- Systematic Listing
- Pure Maths
- ASA Theorem
- Absolute Value Equations and Inequalities
- Addition and Subtraction of Rational Expressions
- Addition, Subtraction, Multiplication and Division
- Algebra
- Algebraic Fractions
- Algebraic Notation
- Algebraic Representation
- Analyzing Graphs of Polynomials
- Angle Measure
- Angles
- Angles in Polygons
- Approximation and Estimation
- Area and Circumference of a Circle
- Area and Perimeter of Quadrilaterals
- Area of Triangles
- Argand Diagram
- Arithmetic Sequences
- Average Rate of Change
- Bijective Functions
- Binomial Expansion
- Binomial Theorem
- Chain Rule
- Circle Theorems
- Circles
- Circles Maths
- Combination of Functions
- Combinatorics
- Common Factors
- Common Multiples
- Completing the Square
- Completing the Squares
- Complex Numbers
- Composite Functions
- Composition of Functions
- Compound Interest
- Compound Units
- Conic Sections
- Construction and Loci
- Converting Metrics
- Convexity and Concavity
- Coordinate Geometry
- Coordinates in Four Quadrants
- Cubic Function Graph
- Cubic Polynomial Graphs
- Data transformations
- De Moivre's Theorem
- Deductive Reasoning
- Definite Integrals
- Deriving Equations
- Determinant of Inverse Matrix
- Determinants
- Differential Equations
- Differentiation
- Differentiation Rules
- Differentiation from First Principles
- Differentiation of Hyperbolic Functions
- Direct and Inverse proportions
- Disjoint and Overlapping Events
- Disproof by Counterexample
- Distance from a Point to a Line
- Divisibility Tests
- Double Angle and Half Angle Formulas
- Drawing Conclusions from Examples
- Ellipse
- Equation of Line in 3D
- Equation of a Perpendicular Bisector
- Equation of a circle
- Equations
- Equations and Identities
- Equations and Inequalities
- Estimation in Real Life
- Euclidean Algorithm
- Evaluating and Graphing Polynomials
- Even Functions
- Exponential Form of Complex Numbers
- Exponential Rules
- Exponentials and Logarithms
- Expression Math
- Expressions and Formulas
- Faces Edges and Vertices
- Factorials
- Factoring Polynomials
- Factoring Quadratic Equations
- Factorising expressions
- Factors
- Finding Maxima and Minima Using Derivatives
- Finding Rational Zeros
- Finding the Area
- Forms of Quadratic Functions
- Fractional Powers
- Fractional Ratio
- Fractions
- Fractions and Decimals
- Fractions and Factors
- Fractions in Expressions and Equations
- Fractions, Decimals and Percentages
- Function Basics
- Functional Analysis
- Functions
- Fundamental Counting Principle
- Fundamental Theorem of Algebra
- Generating Terms of a Sequence
- Geometric Sequence
- Gradient and Intercept
- Graphical Representation
- Graphing Rational Functions
- Graphing Trigonometric Functions
- Graphs
- Graphs and Differentiation
- Graphs of Common Functions
- Graphs of Exponents and Logarithms
- Graphs of Trigonometric Functions
- Greatest Common Divisor
- Growth and Decay
- Growth of Functions
- Highest Common Factor
- Hyperbolas
- Imaginary Unit and Polar Bijection
- Implicit differentiation
- Inductive Reasoning
- Inequalities Maths
- Infinite geometric series
- Injective functions
- Instantaneous Rate of Change
- Integers
- Integrating Polynomials
- Integrating Trig Functions
- Integrating e^x and 1/x
- Integration
- Integration Using Partial Fractions
- Integration by Parts
- Integration by Substitution
- Integration of Hyperbolic Functions
- Interest
- Inverse Hyperbolic Functions
- Inverse Matrices
- Inverse and Joint Variation
- Inverse functions
- Iterative Methods
- Law of Cosines in Algebra
- Law of Sines in Algebra
- Laws of Logs
- Limits of Accuracy
- Linear Expressions
- Linear Systems
- Linear Transformations of Matrices
- Location of Roots
- Logarithm Base
- Logic
- Lower and Upper Bounds
- Lowest Common Denominator
- Lowest Common Multiple
- Math formula
- Matrices
- Matrix Addition and Subtraction
- Matrix Determinant
- Matrix Multiplication
- Metric and Imperial Units
- Misleading Graphs
- Mixed Expressions
- Modulus Functions
- Modulus and Phase
- Multiples of Pi
- Multiplication and Division of Fractions
- Multiplicative Relationship
- Multiplying and Dividing Rational Expressions
- Natural Logarithm
- Natural Numbers
- Notation
- Number
- Number Line
- Number Systems
- Numerical Methods
- Odd functions
- Open Sentences and Identities
- Operation with Complex Numbers
- Operations with Decimals
- Operations with Matrices
- Operations with Polynomials
- Order of Operations
- Parabola
- Parallel Lines
- Parametric Differentiation
- Parametric Equations
- Parametric Integration
- Partial Fractions
- Pascal's Triangle
- Percentage
- Percentage Increase and Decrease
- Percentage as fraction or decimals
- Perimeter of a Triangle
- Permutations and Combinations
- Perpendicular Lines
- Points Lines and Planes
- Polynomial Graphs
- Polynomials
- Powers Roots And Radicals
- Powers and Exponents
- Powers and Roots
- Prime Factorization
- Prime Numbers
- Problem-solving Models and Strategies
- Product Rule
- Proof
- Proof and Mathematical Induction
- Proof by Contradiction
- Proof by Deduction
- Proof by Exhaustion
- Proof by Induction
- Properties of Exponents
- Proportion
- Proving an Identity
- Pythagorean Identities
- Quadratic Equations
- Quadratic Function Graphs
- Quadratic Graphs
- Quadratic functions
- Quadrilaterals
- Quotient Rule
- Radians
- Radical Functions
- Rates of Change
- Ratio
- Ratio Fractions
- Rational Exponents
- Rational Expressions
- Rational Functions
- Rational Numbers and Fractions
- Ratios as Fractions
- Real Numbers
- Reciprocal Graphs
- Recurrence Relation
- Recursion and Special Sequences
- Remainder and Factor Theorems
- Representation of Complex Numbers
- Rewriting Formulas and Equations
- Roots of Complex Numbers
- Roots of Polynomials
- Roots of Unity
- Rounding
- SAS Theorem
- SSS Theorem
- Scalar Triple Product
- Scale Drawings and Maps
- Scale Factors
- Scientific Notation
- Second Order Recurrence Relation
- Sector of a Circle
- Segment of a Circle
- Sequences
- Sequences and Series
- Series Maths
- Sets Math
- Similar Triangles
- Similar and Congruent Shapes
- Simple Interest
- Simplifying Fractions
- Simplifying Radicals
- Simultaneous Equations
- Sine and Cosine Rules
- Small Angle Approximation
- Solving Linear Equations
- Solving Linear Systems
- Solving Quadratic Equations
- Solving Radical Inequalities
- Solving Rational Equations
- Solving Simultaneous Equations Using Matrices
- Solving Systems of Inequalities
- Solving Trigonometric Equations
- Solving and Graphing Quadratic Equations
- Solving and Graphing Quadratic Inequalities
- Special Products
- Standard Form
- Standard Integrals
- Standard Unit
- Straight Line Graphs
- Substraction and addition of fractions
- Sum and Difference of Angles Formulas
- Sum of Natural Numbers
- Surds
- Surjective functions
- Tables and Graphs
- Tangent of a Circle
- The Quadratic Formula and the Discriminant
- Transformations
- Transformations of Graphs
- Translations of Trigonometric Functions
- Triangle Rules
- Triangle trigonometry
- Trigonometric Functions
- Trigonometric Functions of General Angles
- Trigonometric Identities
- Trigonometric Ratios
- Trigonometry
- Turning Points
- Types of Functions
- Types of Numbers
- Types of Triangles
- Unit Circle
- Units
- Variables in Algebra
- Vectors
- Verifying Trigonometric Identities
- Writing Equations
- Writing Linear Equations
- Statistics
- Bias in Experiments
- Binomial Distribution
- Binomial Hypothesis Test
- Bivariate Data
- Box Plots
- Categorical Data
- Categorical Variables
- Central Limit Theorem
- Chi Square Test for Goodness of Fit
- Chi Square Test for Homogeneity
- Chi Square Test for Independence
- Chi-Square Distribution
- Combining Random Variables
- Comparing Data
- Comparing Two Means Hypothesis Testing
- Conditional Probability
- Conducting a Study
- Conducting a Survey
- Conducting an Experiment
- Confidence Interval for Population Mean
- Confidence Interval for Population Proportion
- Confidence Interval for Slope of Regression Line
- Confidence Interval for the Difference of Two Means
- Confidence Intervals
- Correlation Math
- Cumulative Distribution Function
- Cumulative Frequency
- Data Analysis
- Data Interpretation
- Degrees of Freedom
- Discrete Random Variable
- Distributions
- Dot Plot
- Empirical Rule
- Errors in Hypothesis Testing
- Estimator Bias
- Events (Probability)
- Frequency Polygons
- Generalization and Conclusions
- Geometric Distribution
- Histograms
- Hypothesis Test for Correlation
- Hypothesis Test for Regression Slope
- Hypothesis Test of Two Population Proportions
- Hypothesis Testing
- Inference for Distributions of Categorical Data
- Inferences in Statistics
- Large Data Set
- Least Squares Linear Regression
- Linear Interpolation
- Linear Regression
- Measures of Central Tendency
- Methods of Data Collection
- Normal Distribution
- Normal Distribution Hypothesis Test
- Normal Distribution Percentile
- Paired T-Test
- Point Estimation
- Probability
- Probability Calculations
- Probability Density Function
- Probability Distribution
- Probability Generating Function
- Quantitative Variables
- Quartiles
- Random Variables
- Randomized Block Design
- Residual Sum of Squares
- Residuals
- Sample Mean
- Sample Proportion
- Sampling
- Sampling Distribution
- Scatter Graphs
- Single Variable Data
- Skewness
- Spearman's Rank Correlation Coefficient
- Standard Deviation
- Standard Error
- Standard Normal Distribution
- Statistical Graphs
- Statistical Measures
- Stem and Leaf Graph
- Sum of Independent Random Variables
- Survey Bias
- T-distribution
- Transforming Random Variables
- Tree Diagram
- Two Categorical Variables
- Two Quantitative Variables
- Type I Error
- Type II Error
- Types of Data in Statistics
- Variance for Binomial Distribution
- Venn Diagrams

Often in mathematics and related fields like computer science, it is important to be able to make decisions at multiple stages based on associated costs. These could be time costs, resource costs, monetary costs, or really any other cost at all (like feeding your friends pizza if they help you move furniture). How can you make sure to find an optimal path through a field of possible decisions? Well, one method is **dynamic programming**.

So what exactly is dynamic programming?

**Dynamic Programming **is a recursive technique for finding optimal routes through multi-stage decision-making processes from a defined starting point to the desired endpoint.

So far, there has been a lot of talk of 'multi-stage decision making' and 'costs' and all sorts; it's all been rather abstract. Let's try and make this all bit more concrete by visualising it.

The diagram below represents a multi-stage decision process. Each circle with a letter inside is known as a **node**. The arrows indicate the ways in which you may move from node to node. The numbers represent the associated **cost** of each move. With this information, dynamic programming can be used to find an optimal path between \( A \) and \( G \), depending on what we are optimising for.

The simplest way to envisage cost at this stage is to simply imagine it as a distance (which it may often be). The aim may be to find the path from \(A\) to \(G\) over the shortest distance, or perhaps over the longest distance.

Before diving into exactly how this works though, let's compare dynamic programming with another sort of optimisation technique you may have come across.

Ok so hopefully now you've got a better idea of what exactly dynamic programming is, but how does it compare to **linear programming**?

You might remember that linear programming is also a method used in mathematics to find optimal solutions to problems. However, where linear programming is useful in finding a single optimal solution based on constraints such as supply, demand, or budget. Dynamic programming is useful in finding the optimal path through a network of decisions.

For instance, linear programming would be a great choice if you wanted to find the laptop in the store with the optimal amount of processing power for the minimal price.

Dynamic programming would be far more useful if you wanted to find the optimal route through a city to get from point \(A\) to point \(B\). Got that? Great! Well, let's move on to some dynamic programming examples to test what you've learnt.

Dynamic programming works on the principle that for a given problem, any part of an optimised path is itself an optimised path of its own sub-problem. This is known as the principle of optimality.

Take, for instance, the example below. If you wanted to get from \(A\) to \( E \) over the shortest distance, which route would you take? You'd likely say

\[S \to A \to C \to T.\]

and you would be right. What then, is the shortest path from \(S\) to \(T\)? The principle of optimality states that it will be a part of this larger optimal path, and we can see from inspection that this is true. The shortest path is

\[S \to A \to C.\]

Dynamic programming uses this principle to its advantage. By working backwards from the end-point, it can determine the optimal path.

But, you might be thinking, that's all well and good when there are only five nodes, but how on Earth am I supposed to keep that all in my head when there eight, ten, thirty? That's where dynamic programming tables come in. Let's take a look at an example to see how they work.

Take the network below. How can you find the optimal shortest path from \(S\) to \(T\)?

First, construct a table with the following columns.

Table 1 - Start of dynamic programming table.

Stage | State | Action | Destination | Value |

Starting off from the nodes adjacent to \(T\), fill in the table like so.

Table 2 - Dynamic programming table with nodes adjacent to \(T\).

Stage | State | Action | Destination | Value |

\(1\) | \(D\) | \(DT\) | \(T\) | \(2^*\) |

\(1\) | \(B\) | \(BT\) | \(T\) | \(4^*\) |

\(1\) | \(E\) | \(ET\) | \(T\) | \(3^*\) |

The first row that's filled in simply means, starting from \(D\) and moving to \(T\) has a value of \(2\). These are all stage \(1\) moves, as they one move away from the endpoint, \(T\). Mark the optimal action for each state with *.

Now do the same in your table for stage \(2\).

Table 3 - Dynamic programming table stage \(2\).

Stage | State | Action | Destination | Value |

\(2\) | \(A\) | \(AD\) | \(D\) | \(3+2 = 5^*\) |

\(2\) | \(B\) | \(BD\) | \(D\) | \(1+2 = 3^*\) |

\(2\) | \(B\) | \(BT\) | \(T\) | \(4\) |

\(2\) | \(B\) | \(BE\) | \(E\) | \(1+3 = 4\) |

\(2\) | \(C\) | \(CE\) | \(E\) | \(4+3 = 7^*\) |

Notice that the value from each action is the total value to get to \(T\). For the action \(AD\) in the first row, the value is \(3\) to get to \(D\), and then from \(D\) the optimal value to \(T\) is \(2\) (from stage \(1\)) - hence a final value of \(3+2 = 5\).

Now do the same in your table for stage \(3\).

Table 4 - Dynamic programming table stage \(3\)

Stage | State | Action | Destination | Value |

\(3\) | \(S\) | \(SA\) | \(A\) | \(3+5 = 8^*\) |

\(3\) | \(S\) | \(SB\) | \(B\) | \(5+3 = 8^*\) |

\(3\) | \(S\) | \(SC\) | \(C\) | \(2+7 = 9\) |

So, there are in fact **two** equally optimal paths through this network, each with a value (cost) of \(8\). By tracking back through the table, following the *s, you can find and write down the optimal path(s) from \(S\) to \(T\).

For example, looking at stage \(3\), you can see that one of the optimal paths goes \(S \to B\). Going to \(B\) in stage two, you can see that the optimal path from \(B\) goes \(B\to D\). And finally going to stage \(1\) the optimal path from \(D\) goes \(D\to T\).

The optimal paths are therefore

\[S \to A \to D \to T\]

\[S \to B \to D \to T.\]

This technique can be used both to minimise the value of the route or maximise the value of the route. But there's more; dynamic programming can also be used for maximin and minimax problems. What are maximin and minimax problems? Good question.

**Maximin** and **minimax** problems are types of problems that are concerned not with the value of the entire route, but with the maximum or minimum values of each stage.

For **minimax problems**, the maximum value of a stage of the route must be as small as possible.

For **maximin problems**, the minimum value of a stage of the route must be as large as possible.

Luckily, these problems can both be solved in a similar fashion to the problem you solved previously, with a little tweak that is. Let's take a look at the same network and see how the route differs when we approach it as a minimax problem.

Once again, construct the table.

Table 5 - Start of dynamic programming table.

Stage | State | Action | Destination | Value |

Now, fill in stage one as before.

Table 6 - Dynamic programming table stage \(1\).

Stage | State | Action | Destination | Value |

\(1\) | \(D\) | \(DT\) | \(T\) | \(2^*\) |

\(B\) | \(BT\) | \(T\) | \(4^*\) | |

\(E\) | \(ET\) | \(T\) | \(3^*\) |

Now, at stage two things are a little different. Instead of adding the stage one and stage two values to find the total for each action, compare them instead, and choose the maximum. For each state, mark the action with the smaller value with a *.

Table 7 - Dynamic programming table stage \(2\).

Stage | State | Action | Destination | Value |

\(2\) | \(A\) | \(AD\) | \(D\) | \(\text{Max}(3,2) = 3^*\) |

\(B\) | \(BD\) | \(D\) | \(\text{Max}(1,2) = 2^*\) | |

\(BE\) | \(E\) | \(\text{Max}(1,3) = 3\) | ||

\(C\) | \(CE\) | \(E\) | \(\text{Max}(4,3) = 4^*\) |

Now finally do the same for stage three.

Table 8 - Dynamic programming table stage \(3\).

Stage | State | Action | Destination | Value |

\(3\) | \(S\) | \(SA\) | \(A\) | \(\text{Max}(3,3) = 3^*\) |

\(SB\) | \(B\) | \(\text{Max}(5,3) = 5\) | ||

\(SC\) | \(C\) | \(\text{Max}(3,4) = 4\) |

Now, following the *s back through the table, you can find the path that minimises the maximum stage value.

\[S\to A \to D \to T\]

See what you did? For each state, you find the maximum value of a stage that you will encounter from each potential action, and then choose the smaller one.

If the problem were instead a maximin problem, you would do the opposite. You would compare for the minimum value, and then choose the action with the largest one.

Let's take a look at some more examples to make sure you've got this!

Using dynamic programming, find the maximised route through the following network.

Answer:

Fill in the table, placing a * next to the optimal action from each state. In this instance, the optimal action is the one with the highest value.

Table 9 - Network dynamic programming table

Stage | State | Action | Destination | Value |

\(1\) | \(F\) | \(FT\) | \(T\) | \(4\) |

\(G\) | \(GT\) | \(T\) | \(2\) | |

\(H\) | \(HT\) | \(T\) | \(2\) | |

\(2\) | \(D\) | \(DF\) | \(F\) | \(1+4 = 5^*\) |

\(DG\) | \(G\) | \(2+2 = 4\) | ||

\(E\) | \(EG\) | \(G\) | \(1+2 = 3^*\) | |

\(EH\) | \(H\) | \(1+2 = 3^*\) | ||

\(3\) | \(A\) | \(AD\) | \(D\) | \(2+5 = 7^*\) |

\(B\) | \(BD\) | \(D\) | \(3+5 = 8^*\) | |

\(BE\) | \(E\) | \(2+3 = 5\) | ||

\(C\) | \(CE\) | \(E\) | \(3+3 = 6^*\) | |

\(4\) | \(S\) | \(SA\) | \(A\) | \(4+7 = 11^*\) |

\(SB\) | \(B\) | \(2+8 = 10\) | ||

\(SC\) | \(C\) | \(4+10\) |

Following the *s back through the table, the optimal route with the maximum value is

\[S \to A \to D \to F \to T.\]

Let's take another example.

A train company wishes to find the route between station \(S\) and station \(T\) with the largest minimum distance between any two stations. The stations and distances in miles between are shown below.

Find the optimal route for the train company's brief.

Answer:

First, identify that this is a minimax problem.

Now, construct and fill out the table accordingly.

Table 10 - Route dynamic programming table

Stage | State | Action | Destination | Value |

\(1\) | \(F\) | \(FT\) | \(T\) | \(70^*\) |

\(G\) | \(GT\) | \(T\) | \(25^*\) | |

\(H\) | \(HT\) | \(T\) | \(32^*\) | |

\(I\) | \(IT\) | \(T\) | \(45^*\) | |

\(2\) | \(C\) | \(CF\) | \(F\) | \(\text{Min}(13,70) = 13\) |

\(CG\) | \(G\) | \(\text{Min}(22,25) = 22^*\) | ||

\(D\) | \(DG\) | \(G\) | \(\text{Min}(12,25) = 12\) | |

\(DH\) | \(H\) | \(\text{Min}(29,32) = 29^*\) | ||

\(E\) | \(EH\) | \(H\) | \(\text{Min}(5,32) = 5\) | |

\(EI\) | \(I\) | \(\text{Min}(18,45) = 18^*\) | ||

\(3\) | \(A\) | \(AC\) | \(C\) | \(\text{Min}(15,22) = 15\) |

\(AD\) | \(D\) | \(\text{Min}(27,19) = 27^*\) | ||

\(B\) | \(BD\) | \(D\) | \(\text{Min}(23,29) = 23^* \) | |

\(BE\) | \(\text{Min}(20,18) = 18\) | |||

\(4\) | \(S\) | \(SA\) | \(A\) | \(\text{Min}(10,27) = 10\) |

\(SB\) | \(B\) | \(\text{Min}(35,23) = 23^*\) |

Following the *s back through the table, the optimal route with the largest minimum distance between two stations is

\[S \to B \to D \to H \to T.\]

This has been a brief overview of how you can use dynamic programming to tackle different sorts of problems. Why not head over to our other explanations on dynamic programming, like Shortest and Longest Path Problems, to see each of these types of problems covered in more depth?

- Dynamic programming is a recursive technique for finding optimal routes in multistage decision processes.
- Dynamic programming works on the principle that for a given problem, any part of an optimised path is itself an optimised path of its own sub-problem.
- Dynamic programming can be used to solve shortest and longest path problems.
- Dynamic programming can also be used to solve minimax and maximin problems.

**Dynamic Programming **is a recursive technique for finding optimal routes through multi-stage decision-making processes from a defined starting point to the desired endpoint.

To practice dynamic programming, just do lots of questions and examples.

There are two types of dynamic programming - the top-down approach and the bottom-up approach.l

More about Dynamic Programming

Be perfectly prepared on time with an individual plan.

Test your knowledge with gamified quizzes.

Create and find flashcards in record time.

Create beautiful notes faster than ever before.

Have all your study materials in one place.

Upload unlimited documents and save them online.

Identify your study strength and weaknesses.

Set individual study goals and earn points reaching them.

Stop procrastinating with our study reminders.

Earn points, unlock badges and level up while studying.

Create flashcards in notes completely automatically.

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.

Over 10 million students from across the world are already learning smarter.

Get Started for Free