Dynamic Programming21 sections · 916 units
Open in Course

Intro

What you'll learn

You've learned how to solve 0/1 knapsack, unbounded knapsack, and value-based state design. Those cover maybe 30% of knapsack problems you'll see. The rest are variations that twist the core idea in specific ways.

I'll show you four major variations: boolean DP (can we reach this sum?), counting DP (how many ways?), bounded knapsack (limited copies), and multi-dimensional knapsack (multiple constraints). By the end, you'll recognize which variation a problem needs and know exactly how to adapt your state design. Let's start with the most common twist: subset sum.