I was going over the DP presentation, specifically the question with the best way to return change (fewest coins). I think that the recursive definition is not completely correct - we should add 1 and not the value of the coin (a_i) to the minimum over all smaller sub problems, correct (we are asked to return the amount of coins in the optimal solution)?
Date: 25 Jun 2014 15:46
Number of posts: 3
RSS: New posts
thanks, I thought I had uploaded the correct version but I hadn't - it's now been corrected
The presentations on the website are still adding a_i..
Furthermore, shouldn't we define c = 0?
otherwise when we calculate c[ak] (for the coin ak), we try to calculate c and we can get inf (instead of 1)