Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 474 Ones and Zeroes - Two Capacities

3D state

Define dp[i][j]dp[i][j] = max strings selectable using at most ii zeros and jj ones. Your answer is dp[m][n]dp[m][n]. For each string with zz zeros and oo ones, the formula is: dp[i][j]=max(dp[i][j],dp[iz][jo]+1)dp[i][j] = \max(dp[i][j], dp[i-z][j-o] + 1).

Process each string and update the 2D (two-dimensional) DP array backwards (from mm down to zz, from nn down to oo) to avoid reusing the same string. It's the same backwards-loop trick from 0/1 knapsack, just in two dimensions.