Base Case and First Rows - Knapsack and the DP Table

The DP table begins with a row for using no items. The next row shows how the first item changes every capacity. These rows make the recurrence concrete before the full table is filled.

highlighted = computed this step

Base row

With no items, every capacity has value 0. Why: there is nothing available to put in the bag.

dp[0,w]=0

First item row

After the first item, each positive capacity can reach value 1. Why: the item fits as soon as capacity reaches its weight.

\text{first row value }1

Diagram note

The displayed prefix is clipped from the recomputed DP table; only the first two rows are shown here. Pixel positions are rounded for layout; every number shown is exact.

\text{base cases anchor the table}