Dynamic Programming – Recurrence Relationships of PD: Currency Exchange vs Backpack


  1. Relation ratio KP

$ max { [v + f(k-1,g-w ), f(k-1,g)] $ yes w <= g and k>0

  1. Relation of PCC recurrence

$ min {[1 + f(r,c-v), f(r-1,c)]$ yes v <= c and r>0

I do not understand (as much as I've investigated) exactly what is the reasoning behind KP comparing in both cases (take the element / do not take it) to the previous row $ (& # 39; k-1 & # 39;) $ while CCP only does this when it does not take the coin (the same number that is up in the same column persists).

To evaluate the case in which the coin is taken, CCP says to return to the same row as many columns as it obtains by subtracting the value of the currency from that row of the column in which it is located. Then he says add 1 (because you would be taking the coin).

Assuming you understood this well enough, this last logic makes a lot of sense to me. I do not see the need for KP to go up a row when taking the element (I see why it adds & # 39; v & # 39; back several columns, it's just the $ & # 39; k-1 & # 39; $ that puzzles me

What is the logic behind this?