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 :)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 :)
Name |
---|
could anyone provide all the atcoder contests with editorials
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:
thanks a lot mate for giving the reply and ur time besides some people waste time downvoting others .
If I understand correctly, does this mean that distributing DP couldn't be used in top down DP?
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} $$$
For 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] $$$.
For 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.