Dynamic Programming: the Rod Cutting Problem

Table of Contents:

00:00 - Introduction and Prerequisites
00:19 - Rod Cutting Problem Definition
00:36 - Dynamic Programming Template
01:02 - Recursive Solution Design
04:02 - Recursive Solution
05:02 - Recursive Tree
05:56 - Parameter Analysis
06:19 - Memoized, Top-Down Dynamic Program
06:49 - Memoized Tree
07:35 - Iterated, Bottom-Up Dynamic Program
08:27 - Reconstructing the Optimal Cuts
09:19 - Wrap-Up

Thanks to Cydni Turner for noticing a really bad cut-and-paste error on a previous version (which caused me to republish this version), and to Saniya Godil for noticing that I didn't initialize everything, luckily getting that fix in time for this version too.