I’m studying the famous making change problem. (Post 1 and Post2).
Suppose you were given three coins (1, 2, and 5) and a bill of amount 10 and you want to compute the number of ways you could exchange the bill into coins. In this specific example, there are 4 ways.
The solution involves ordering the coins from the largest to the smallest (5, 2, 1). We then can divide the solution into three subproblems:
(1) the number of ways to change using coins (1) and amount (10 – 1). Call it $ F_1(10-1)$ .
(2) the number of ways to change using coins (1,2) and amount (10 – 2). Call it $ F_2(10-2)$ .
(3) the number of ways to change using coins (1,2,5) and amount (10 – 5). Call it $ F_3(10-5)$ .
The final recurrence would be $ F(10) = F_1(10-1) + F_2(10-2) + F_3(10-5)$ .
I understand the intuition and usually dynamic programming problems have very straight forward proofs (Cut and Paste Arugments). But with this problem, I have no idea where to start? The proof is usually by contradiction and arguing how it’s not possible for $ F(n)$ not to be the optimal value. But I’m not sure here. Any hints on how to even start with this proof? Basically, why is the above recurrence correct?