Respuesta :
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.
