Dynamic Programming21 sections · 916 units
Open in Course

0/1 Knapsack - Base Cases

Empty foundations

Start with the simplest cases. If you have zero items, the best value is zero regardless of capacity: dp[0][w]=0dp[0][w] = 0 for all ww from 00 to WW. If you have zero capacity, you can't take anything: dp[i][0]=0dp[i][0] = 0 for all ii from 00 to nn.

These base cases fill the first row and first column of your DP table. Everything else builds from here. This is where recursion stops. Without it, you get infinite recursion and a stack overflow. Every recursive solution needs at least one base case.