Skip to content
CCC Python Course

Memoization and introductory dynamic programming

Stage
4
Module
M4.11
Lessons
1

In this module

  • Recognize when a recursive function recomputes the same subproblems.
  • Use memoization to cache results and avoid redundant work.
  • Reframe a memoized recursion as dynamic programming building up from smaller subproblems.
  • Understand why this transforms exponential time into polynomial time.

Before this module

M1.14Recursion fundamentalsM2.5Brute force and complete search

Lessons

  1. 1Memoization and introductory dynamic programming

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2015 J5
    π-day (opens on DMOJ in a new tab) DMOJ

    Count the ways to reach a target using memoized recursion over smaller subproblems.