kanisht_09's blog

Distributing dp or Receiving dp
By kanisht_09, history, 4 years ago, In English

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 :)

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

could anyone provide all the atcoder contests with editorials

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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];
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

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

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply