Блог пользователя kaiyu

Why this isn't 1-D dp ?
Автор kaiyu, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить