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

Автор kanisht_09, история, 4 года назад, По-английски

Can someone please explain elaborately distributing dp. I found it in the editorial of atcoder problem Leaping Tak. Given below is the editorial link : https://atcoder.jp/contests/abc179/editorial/133

Thanks in advance :)

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

could anyone provide all the atcoder contests with editorials

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Distributing DP means that you take information about the current state, and pass it to future states.

Receiving DP means that you take information from previous states.

For example, if you're implementing a DP solution for finding the Fibonacci numbers, you could do either one:

dp[0]=0;
dp[1]=1;
// receiving DP
for(int i=2;i<n;i++){
  dp[i]=dp[i-1]+dp[i-2];
}
// distributing DP
for(int i=0;i<n;i++){
  dp[i+1]+=dp[i];
  dp[i+2]+=dp[i];
}
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    thanks a lot mate for giving the reply and ur time besides some people waste time downvoting others .

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

    If I understand correctly, does this mean that distributing DP couldn't be used in top down DP?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

Distributing dp is also often referred to as push dp, and receiving dp is also called pull dp.

To briefly go over the differences between them, let's consider this problem.

In both methods, our definition of dp is the same, $$$ dp[x] = \text{minimum number of coins required to make value x} $$$

Push dp
Pull dp

Additional Note: If you think about these methods, you realise the importance about order of processing. If the dp for your current state is not optimally calculated, and you push from there, and later optimally compute the dp for the state, then you can see that you would probably not get the optimal overall result. Thus, it leads you to the idea of a topological ordering of states, according to dependence on other states' results.