kanisht_09's blog

By kanisht_09, history, 3 months ago,

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

 » 3 months ago, # | ← 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 dpFor push dp, you push results from currently available results.so, if you consider adding coin with value $c$ to your knapsack, and considering you already have the optimal value for some $x$ in $dp[x]$then, from using $dp[x]$ coins to make value $x$, you can transition to, using $dp[x]+1$ coins to make value $x+c$,more programatically, we update $dp[x+c] = min( dp[x+c], dp[x] + 1 )$.Notice how we "pushed" from an already computed value $dp[x]$ to $dp[x+c]$. Pull dpFor pull dp, you pull results for the current state, from previously computed results.you want to consider computing $dp[x]$, let's say the last coin used to get to the current state was of value $c$, then your update looks like, $dp[x] = min( dp[x], dp[x-c] + 1 );$Here, you pull the results from already computed value of $dp[x-c]$.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.