Given an unlimited supply of coins of denomination x1, x2, ..., xn, we wish to make change for a value v. Weare seeking an O (nv) dynamic-programming for the following problemInput: x1, ..., xn; vQuestion: Is it possible to make change for v using coins of denominations x1, ..., xn

Answer

C (t) = min

x∈{x1, ..., xn}

C (t - x) + 1

Step-by - step Solution

Subtasks. For any 1 ≤ t ≤ v, let C (t) = c where c is the minimum number of coins required to create the

total t, using the given denominations. If it is not possible for any number of coins, then C (t) = ∞.

Recurrence Relation. We calculate C (t) based on C (s) for 1 ≤ s < t. The recurrence relation is:

C (t) = min

x∈{x1, ..., xn}

C (t - x) + 1

Base Case, Final Solution, Evaluation Order. We initialize C (0) = 0. We also declare that C (u) = ∞

when u < 0. The final solution is just whether C (v) is less than or equal to k. The evaluation order is to

start at t = 1, compute C (t), increment t and repeat.

Correctness. We will show by induction that the subtask C (t) is correctly computed for all t. The base

case C (0) = 0 is true: by using 0 coins, we have a total of 0, and 0 coins is the least we could possibly use.

For the inductive case, observe that for any x ∈ {x1, ..., xn}, given a way to produce a total t-x with c coins,

we may produce a total t using c + 1 coins, so we know C (t) ≤ 1 + C (t - x). As we wish to minimize the

total coins used, we care only about the minimal way to construct the value t-x and our use of the previous

subtask is correct. We take the minimum over all n possibilities. This is exhaustive: every combination of

c + 1 coins totalling t can be decomposed into a combination of c coins and an extra final coin. We remark

that C (t - x) = ∞ means C (t - x) + 1 is also ∞, and that the minimum in the recurrence relation will

be infinite if and only if all C (t - x) are infinite, which implies there is no valid way to create the total t.

Thus C (t) is correctly computed. Our evaluation order is also correct, as computing C (t) requires only the

precomputed values C (s) for s < t.