kaiyu's blog

Why this isn't 1-D dp ?
By kaiyu, history, 6 years ago, In English

Problem Link:

https://www.codechef.com/problems/GRHARSH

I see all the solutions have 2D dp solution.

I was thinking dp[i] = max gold at the time i.

Is this correct?How to solve it using 1-D dp?

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

Comments Comments (3)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

It's never why isn't it $$$1D$$$ dp. Dp only depends on the necessary information. Can you compress all the necessary information in $$$1$$$ dimension. If you can't think of any such value, it's probably not. The necessary information is the amount of gold you can earn if the subarray left is $$$l$$$ to $$$r$$$. The $$$l$$$ and $$$r$$$ values are probably the $$$2$$$ Dimensions, and it stores the maximum amount of gold you can get if you reach this state.

dp[i] = max gold at the time i.

Let's look at why this is an incomplete state.

The example test case is 1 2 3 4 5. If you just want the max gold at time $$$1$$$, you would choose $$$5$$$. However that is not optimal because you need to wait until the last turn.

i cannot see any recurrence relation that allows us to only use the maximum gold at time $$$i$$$.

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

    I would choose the min value first so that jars which had greater initial value will get time to fill themselves ? So i would start with 1 then 2 then 3 and so on till 5.

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

      Try :

      $$$10^9,\ 1,\ 2,\ 3,\ 10^9-1,\ 10^9-1,\ 10^9-1$$$

      Your approach is more like a greedy solution. If you want to check whether a greedy is correct, think of a test-case where your assumption is incorrect. Though while practicing, you should be able to prove it formally.

      → Reply