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]\) (đoạn có thể rỗng nếu \(ans[i - 1] \le 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)\).