 Solution

In the coin change problem, take denominations $\{1,3,4\}$ and target amount $6$. The natural greedy algorithm repeatedly chooses the largest denomination not exceeding the remaining amount. It chooses $4$, then $1$, then $1$, for three coins. Yet $3+3=6$ uses only two.

Two is optimal: one coin cannot make $6$ because denomination $6$ is absent, and the displayed pair attains the lower bound. ThereforeThe locally largest first coin loses the possibility of using the better pair of threes. This supplies a concrete failure of the greedy-choice property; optimal substructure alone does not justify the greedy choice. The dynamic programming recurrence from part (b) would compare all feasible first or last denominations and find the pair.