hars123's blog

By hars123, history, 5 weeks ago, In English,

I am finding it difficult to find the relation for transition from one state to another. i.e. if dp[i][j] represents no of ways of distributing j candies among positions [1,i]. Can someone explain what should i think to find that transition. Or i am just unable to observe the pattern.

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

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

Your dp state is correct, to do the transition in O(1) time you need to do the dp calculation iteratively and after you finish for some i, you need to make prefix sums in order to calculate the sum in range [l,r] for i-1 in constant time (O(1) ).

Here is how to implement it:

  • First set the base states, dp[0][0]=1 and dp[0][1...k]=0,

  • Iterate over i from 1 to n and do the following:

  • Make an array of size k and calculate prefix sums of dp[i-1][0...k],

  • Now for every j from 0 to k, you can calculate in O(1) the number of ways to get to state dp[i][j],

  • This is done by finding the sum of dp[i-1][max(0,j-a[i])...j] using the prefix sums.

Here is my implementation of the problem if you need it. (I added comments to the code so you can understand it better :) )

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

In general, DP problems can often be thought of as a decision making process, where you make some "local" decision and your state after that local decision becomes some state you have previously calculated the answer for. So, when you are on a given state, you try all the local decisions you can, and take the one that results in the best answer (or in this case, sum up the number for each local decision to get the total count for the current state).

Your dp state characterization is correct: dp[i][j] represents the number of ways of distributing j candies among the first i people. Now, say you are trying to calculate dp[i][j]. What is the "local decision" that you must make at this state? It will just be how many candies you want to give to the i'th person (in fact, deciding what to do with the i'th person is often the decision that must be made when your dp state deals with "something among the first i people"). So, say you want to give the i'th person k candies, where k is somewhere between 0 and min(ai, j) (we can't give them more than ai candies because of the problem constraint, and can't give them more than j candies because we only have j candies). Then, we see that if we give k candies to person i, then the number of ways to do that is dp[i - 1][j - k] (because we precisely want to find the number of ways to distribute j - k candies to the first i - 1 people). If we sum up these numbers over all the k from 0 to min(ai, j), then we should get the count for dp[i][j].

You'll notice, though, that this results in O(NK) states and O(K) operations per state, or O(NK2) runtime, which is too slow. There is something about the state transitions that allows you to calculate the sum over all the different local decisions much faster, in fact in O(1). Can you think of what to do? Hint: all of the local decisions for a given dp[i][j] recurse into a contiguous block in the dp[i - 1] row.

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

    Is it possible to implement it in a topdown manner ?

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

      I think it technically is, if you keep track of which states you've computed and calculate the prefix sum once you've gotten all of them... but it seems super complicated. Just do bottom up. If you don't usually do bottom up, good; this is a great opportunity to learn, since both top-down and bottom-up are useful to know.

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

    Thank you very much for that detailed description. I would give 10 upvotes if I could. Using words instead of math makes my brain function better :)

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

    Just a quick question. When you see a problem and know its dp. What are your steps to coming up with the solution? I have a lot of trouble with bottom up but am very good at top down dp.

    For me, 1. Establish the state(pretty easy) 2. Establish transition(very difficult for me.. any tips?) 3. Establish base case(easy as well)

    I usually have to draw out the table on paper and try to see if I can find any patterns for the transition. How would you recommend going about finding transitions?

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

      So I think those three steps are pretty good; as for the transition, this is where the "local decisions" come into play. If, at a given state, you can break the problem down into making one of multiple choices (often times it's something as simple as "use this element or don't use this element", like in knapsack), then you look at what states you'll end up with in the case of each one of your choices.

      Also, as you get to more difficult DP problems, establishing the state starts becoming much harder. For example, for this problem, once you get the state down, the transition is pretty simple, but the state is pretty hard to come up with. In my mind, this is the toughest part :)