Sắp xếp mảng tiền xu $coin[]$. Nhận xét rằng nếu xu nhỏ nhất có giá trị lớn hơn $1$ thì $1$ là kết quả bài toán.

Tạo mảng $ans[]$ với ý nghĩa: $ans[i]$ là số tiền nhỏ nhất mà $i$ đồng tiền nhỏ nhất không thể tạo ra. Từ đó ta có công thức truy hồi:

• $ans[0]=1$,

• $ans[i]=ans[i-1]+coin[i-1]$ nếu $i\ge 1$ và $coin[i-1]\le ans[i-1]$

  Khi sử dụng $i-1$ đồng tiền thì các tiền trong đoạn $A:[1,ans[i-1]-1]$ đều có thể tạo ra, sử dụng thêm đồng $coin[i-1]$ các tiền trong đoạn $B:[coin[i-1],ans[i-1]+coin[i-1]-1]$ đều có thể tạo ra. Do $coin[i-1]\le ans[i-1]$, hợp hai đoạn $A$ và $B$ các tiền trong đoạn $[1,ans[i-1]+coin[i-1]-1]$ đều có thể tạo ra, từ đó ta có công thức như trên.

• $ans[i]=ans[i-1]$ nếu $i\ge 1$ và $coin[i-1]>ans[i-1]$.

  Lập luận tương tự, hai đoạn không hợp được thành một trong trường hợp này.

Chú ý rằng do mảng bắt đầu từ chỉ số $0$ nên $coin[i-1]$ là đồng tiền thứ $i$.

Lời giải cài đặt ngắn gọn chỉ sử dụng biến $ans=1$, break vòng lặp nếu $coin[i]>ans$.

ĐPT: $O(n)$.