Dynamic Programming Part 3: Representing State
Channel: Tech Interviews and Competitive Programming Meetup
Date: 2019-08-18

We discuss extensively the concept of "state" or "history", the notion that a DP recurrence needs to capture as function parameters all the information about past choices or history that are necessary to know in order to determine the optimal solution to the remainder of the problem. At the same time, we see that using many function parameters to capture such history often leads to poor time complexity, so the trick to writing good recurrences is to capture the history as minimally and compactly as possible. We look at increasingly elaborate variations on a challenging problem to learn how to write compact and elegant recurrences.

This is Dynamic Programming: Representing State, part 3 of a larger series on Dynamic Programming. It's a recording of a live class that was taught on July 28, 2019 in the Bay Area as part of the Tech Interviews and Competitive Programming Meetup group (https://www.meetup.com/tech-interviews-and-competitive-programming).

Sorry about the little bit of glare on the board. The angle of light reflection off the board was unlucky in this case.