This question is very similar to a 0-1 knapsack, the transition function is
dp(k, x, y) = max(dp(k-1, x-z, y-o) + 1, dp(k-1, x, y)) (z is zeroes in strs[k], o is ones in strs[k])
dp(k, x, y) is the maximum strs we can include when we have x zeros, y ones and only the first k strs are considered.
dp(len(strs), M, N) is the answer we are looking for
I first implemented a dfs + memoization, which gets MLE, so I created a bottom up style dp.
With bottom up, we can use something called "rolling array" to optimize space complexity from O(KMN) to O(MN)
class Solution(object): def findMaxForm(self, strs, m, n): dp = [ * (n+1) for _ in range(m+1)] def count(s): return sum(1 for c in s if c == '0'), sum(1 for c in s if c == '1') for z, o in [count(s) for s in strs]: for x in range(m, -1, -1): for y in range(n, -1, -1): if x >= z and y >= o: dp[x][y] = max(1 + dp[x-z][y-o], dp[x][y]) return dp[m][n]
Could you please explain whats the idea behind the rolling array and how you converted the inductive step to:
dp[x][y] = max(1 + dp[x-z][y-o], dp[x][y])
@Harold-Finch Consider a typical 0-1 knapsack problem,
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), where
dp[i][c] is the max value we can get considering the first
i items being put into a knapsack with capacity
w[i] is the weight of
ith item, and
v[i] is value. A naive implementation of this is to use a 2D array
dp. However, based on the observation that the value of
dp[i][c] is always based on values one row above (
dp[i-1]) and to its left, we don't need to keep all previous computed results (
dp[i-2] and above). If we replace the 2D array,
dp, with 1D array, say
ra, right before starting the
ra contains values from
i-1th iteration. If we iterate
ra from right to left, and when we are trying to compute
ra[j], we can be sure that all elements to the left of
ra[j], are from previous iteration, which are the values we want use. This technique is sometimes referred to as "rolling array". And this problem is a 2D extension of a 1D 0-1 knapsack, and we use "rolling array" to reduce
dp from 3D to 2D.
@mlaw0 Thanks a lot!
@mlaw0 Great solution. One thing I couldn't understand, for the
y loop, why cant we start from lower bound, rather than upper bound ( i.e-
dp(k, x, y) = max(dp(k-1, x-z, y-o) + 1, dp(k-1, x, y))
This is the orignal state transition funciton. The implementation optimize the space complexity. It used only two dimensional array
dp(x, y). Think like this, when at
k iteration(the outer loop), we want to keep
dp(x-z, y-o) and
dp(x,y) are the state at
k-1. Because of this
dp(x, y) is depending on something in front of it
dp(x-z, y-o), that's why we want to loop
n, otherwise at
dp(x-z, y-o)is already updated, are the state at
not sure why but the same code doesn't get accepted on Python3, but does get accepted on Python2
@rohithiitj Same here. OJ seems not working properly for Python solution.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.