サンプル \(1\) の \(X=87\)、\(A=(1,10,100)\) を例として考えます。

\(10\) 円以上の硬貨では \(10\) 円単位のやりとりしかできないので、\(10\) 円未満の端数に関するやり取りは \(1\) 円硬貨で行わなければなりません。このときありえるやり取りとしては「支払いに \(1\) 円硬貨を \(7\) 枚含める」「お釣りとして \(1\) 円硬貨を \(3\) 枚もらう」のどちらかのみを考慮すれば十分です。
前者は \(80\) 円を \(10\) 円以上の硬貨を用いて支払う問題に、後者は \(90\) 円を \(10\) 円以上の硬貨を用いて支払う問題になります。

このように下から順に考えることで、再帰的に問題を解くことができます。
再帰的に問題を解く過程で登場する金額は \(\left\lfloor \frac{X}{A_i}\right\rfloor A_i\) 及び \(\left\lceil \frac{X}{A_i}\right\rceil A_i\) のみなので、メモ化することで計算量は \(O(N)\) になります。

実装例(C++)