sridhar153999's blog

By sridhar153999, history, 6 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Can't view your code. But, there are several ways in which you can optimize space for DP.

  1. 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).

  2. 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thank you ,but i know from that process my dp stte will be (2)(no of zero)( no of one) but i hv seen solution of (no of zero)(no of one) its df from other.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          There are 2 generic ways to do this:

          1. Use two DP tables instead of one. Each representing one layer of the first-dimension in your single-table.

          2. Change the iteration of the inner loop (i.e. the second layer). Continuing from the example in my first comment, if dp[i][j] = dp[i — 1][j] + dp[i — 1][j — 1], notice that the answer also depends on the previous layer and the current layer of the second dimension. So, if you loop over the second dimension in decreasing order and throw away the first layer, you will still compute the correct answer. Why? Draw the 2D table and trace the computation order. It should be quite clear.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is position just num_of_zeroes + num_of_ones?