Provide a dynamic programming algorithm for the following problem:

You decide to write an actual letter to your grandmother --- you know, the physical kind on real piece of paper. After detailing your latest exploits, you discover that you don't actually have any stamps. You hop over to a nearby convenient store, which you seem to recall sells stamps. You figured out that you need n cents of postage, but the store only has stamps in denominations of x₁, x₂, x₃, ..., x_m. Fortunately, x₁ is a 1 cent stamp, so you know you can definitely make n cents out of these stamps. However, you want to cobble together as few stamps as possible.

Describe a dynamic programming algorithm that selects the fewest number of stamps that make up n cents.

Notes:

You want to make exactly n cents of postage --- i.e., do not go over n cents.

Assume the store has an adequate supply of each stamp, so you won't run out.

Example: Suppose n = 14, x₁ = 1, x₂ = 4 and x₃ = 6. You can make up 14 cents using two 4-cent stamps and one 6-cent stamp. If you tried the biggest-first strategy, you would end up with two 6-cent stamps and two 1-cent stamps. That's a worse solution because it uses four stamps instead of three.