HELLO CODERS
i found this dp problem on leetcode (ones and zeros) (https://leetcode.com/problems/ones-and-zeroes/) i solved it using 3 states [position][no_of_zeros][no_of_ones] its giving me memory limit exceeded i saw some people using 2d state [no_of_zeros][no_of_ones] .i cant understand how they come up with their solution .help me explaining their 2 d concept. MY solution link solution although the time complexity of my code and thier code is same.
Can't view your code. But, there are several ways in which you can optimize space for DP.
Inspect the dependency between states. For example if dp[i][j] = dp[i — 1][j] + dp[i — 1][j — 1], observe that the answer depends only on the previous layer of the first dimension. So, if you loop over the first dimension increasing order, you can actually throw away the first layer (provided that you don't need the answers for that layer at the end).
Drop one parameter and recover from another. Let's say that X + Y = 1 and you have dp[X][Y], then you can drop the second dimension and use 1 — X to track the quantity of Y instead.
yes but here they are doing something diffrnt ie from[str.len][no of onws][no of ones] to [no of zero][no of ones]
You should atleast try to read and think about the hints that people give you.
I just tried out the question, and the first trick mentioned by LanceTheDragonTrainer is pretty easy to see. You process each string one at a time, and consider cases where you make this string or not. Update your dp using only the dp calculated till the previous string.
Is position just num_of_zeroes + num_of_ones?