icpc_expert's blog

Dp problem
By icpc_expert, history, 6 years ago, In English

Problem Can anybody help me on how to figure out the dp behind this problem. I have already written a recursive solution for this problem. Also can anybody help me how to see after writing the recursive code that what are the states of the dp.I got too much difficulty in determining the states of a dp solution.

Tags #dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Ok, so the trivial recursive formula we have is f(i, j, k) = minimum time required if i is first in queue, j is second and k is third. The transition is pretty obvious now. We consider three cases:

1) Serve i and j. Now k, k + 1, k + 2 are first three in the queue
2) Serve i and k. Now j, k + 1, k + 2 are first three in the queue and
3) Serve j and k. Now i, k + 1, k + 2 are first three in the queue

Thus we have: f(i, j, k) = min(time_in_case1 + f(k, k + 1, k + 2), time_in_case2 + f(j, k + 1, k + 2), time_in_case3 + f(i, k + 1, k + 2). Answer will be f(1, 2, 3).

But can we do any better? The answer is yes! One has to notice that in any case the third person in the queue will be the one next to the second. This allows us to drop the third argument from our recursive function and recover it just by looking at the second one in the queue. In other words we can set k = j + 1 without passing it as an argument with no need to make any change in our initial formula! All we have to do now is memoize the answer for each i, j when we calculate it for the first time so we don't have to calculate it again.

You can see my accepted code for this problem here.

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

    Thanks a lot for the awesome explanation. But in general i am asking how to look upon the states and check whether the state are depend on the sub-problems or not in this case how the problems are dependent on its sub-problems.

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

      Learning how to determine the DP states is something that can be learned only by practicing on solving DP problems. The more DP problems you solve the easier it gets to determine the states to a new problem. In general, in all DP problems the states will be dependent of smaller subproblems. In our case for example f(i, j) depends on f(j + 1, j + 2), f(i, j + 2) and f(j, j + 2).

      → Reply