Skip to main content
MathidiaMathematics Academy
Operations research
Lesson 52 of 75
Easy practice

Dynamic programming

Objective. Use states and recurrences for staged decisions.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Dynamic programming solves a multi-stage decision problem by defining a value function over states and relating it to earlier stages via a recurrence, exploiting optimal substructure so the best decision now plus the best future decisions gives the overall best outcome. Working backwards from the final stage, each state's value is computed once and stored, avoiding repeated recomputation of overlapping subproblems. For example, to find the cheapest path across stages of a network, compute the cheapest cost-to-go from each node in the last stage first, then each earlier stage using already-solved later values. The final answer is read off the value at the initial state.

Worked example

A dynamic programming stagecoach problem has three stages. From the start, stage 1 costs are 4 (to A) or 6 (to B). From A, stage 2 to the end costs 5; from B, stage 2 to the end costs 3. Use dynamic programming to find the minimum total cost from start to end.

1 … 4
Illustrated card showing 1 … 4
  1. 1Define the state as the current node and compute cost-to-go from the end backwards.
  2. 2From A, the only remaining cost-to-go is 5, so total via A is 4 + 5 = 9.
  3. 3From B, the only remaining cost-to-go is 3, so total via B is 6 + 3 = 9.
  4. 4Compare both paths' totals, 9 and 9, so the minimum total cost is 9.

Answer: 9

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. A frequent error is writing a recurrence that does not satisfy optimal substructure, or re-deriving each subproblem from scratch instead of storing solved state values, which destroys the efficiency that makes dynamic programming worthwhile.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard