二维费用0-1背包问题（LeetCode）DP解法核心疑问咨询

Let’s break down all your questions step by step—this is a classic constrained knapsack problem, and it’s totally normal to get stuck on state transitions and space optimizations at first!

1. Why Do We Subtract zeros and ones in the State Transition? #

First, let’s anchor ourselves to the definition of the dp table:

• dp[i][j] represents the maximum number of strings we can form using up to i zeros and j ones.

When processing a string s that uses zeros zeros and ones ones, we have two choices:

• Skip the string: dp[i][j] stays as its current value (the best count we could get without including s).
• Take the string: To do this, we need enough resources (i >= zeros and j >= ones). If we take s, we consume zeros zeros and ones ones—so we look back at the state where we had i - zeros zeros and j - ones ones. This state tells us the maximum number of strings we could form with the remaining resources before adding s. We add 1 (for the current string) and compare it to the existing dp[i][j] to keep the larger value.

Let’s use your example to make this concrete:
Take the string "10" (1 zero, 1 one). When we process it, for i=1 and j=1, the transition becomes:

dp[1][1] = max(1 + dp[0][0], dp[1][1])

Since dp[0][0] is 0 (no resources = no strings), this becomes max(1, 0) = 1—which makes sense: we can form 1 string ("10") with 1 zero and 1 one.

2. Decoding the DP Table Visualization #

Assuming the first table you’re referring to is the state after processing the first few strings in your example, here’s how to interpret it:

• Axes: Typically, the y-axis corresponds to available zeros (ranging from 0 to m=5), and the x-axis corresponds to available ones (ranging from 0 to n=3). Each cell (i,j) maps directly to dp[i][j].
• The 1s in the table: These cells represent states where we can form exactly 1 string. For example, after processing "10", every cell where i >=1 and j >=1 will have a value of 1—because with at least 1 zero and 1 one, we can choose to include "10" (and no other strings yet). Cells where i <1 or j <1 stay 0, since we don’t have enough resources to form even that one string.

As we process more strings, the table evolves:

• When we process "0001" (3 zeros, 1 one), cells where i >=3 and j >=1 will now consider adding this string. For example, dp[3][1] stays 1 (either take "10" or "0001"—same count), but dp[4][2] jumps to 2 (take both "10" and "0001").
• By the end of processing all strings, the bottom-right cell dp[5][3] holds the maximum count—4 in your example.

3. Understanding the 3D DP to 2D Space Optimization #

Let’s start with the unoptimized 3D approach, which is easier to grasp:

• We’d have a 3D array dp[k][i][j], where k represents how many of the first k strings we’ve considered. The value is the maximum number of strings we can form with i zeros and j ones using the first k strings.
• The state transition would be:

  dp[k][i][j] = max(dp[k-1][i][j], 1 + dp[k-1][i-zeros][j-ones])
  

  Here, dp[k-1][i][j] is the value without using the k-th string, and 1 + dp[k-1][i-zeros][j-ones] is the value if we do use it.

The key optimization insight: to compute dp[k][...], we only need values from dp[k-1][...] (the previous layer). We don’t need to store all k layers—we can overwrite a single 2D array instead.

But we have to iterate backward (from m down to zeros, and n down to ones) instead of forward. Why?

• If we iterate forward, we’d reuse updated values from the same iteration, which would let us select the same string multiple times (turning it into an unbounded knapsack problem).
• By iterating backward, we ensure we always use values from the previous k-1 layer (before we updated the 2D array for the current string), preserving the 0-1 rule: each string can be used at most once.

Your code uses this optimized 2D approach, cutting space complexity from O(k*m*n) to O(m*n)—a huge saving for large inputs.

内容的提问来源于stack exchange，提问作者VickTree