Tessellate S.T.E.M.S - Computer Science - College - Set 2 - Problem 3

In the Wizarding World, the Ministry of Magic decided to introduce a new system of currency to celebrate the downfall of an evil wizard. They decided to have a set of coins with denomination {25, 15, 1}. i.e, the 25 galleon coin, 15 galleon coin and the 1 galleon coin. Given an item worth 'N' galleons, the wizards need to pay using the least number of coins possible. For example if an Owl cots 16 Galleons, then they can pay using 2 coins: one 15 Galleon coin and one 1 Galleon coin, which would be the least number of coins in this case. Which of the following options describe an algorithm that the people in the wizarding world can use to achieve this?

1. Greedy Algorithm: Always selects the coin with the largest denomination not exceeding the remaining sum
2. Divide and Conquer: Divide the coins into half and find the best way to pay for each half, and combine the answer
3. Greedy Algorithm : Always select the coin with the smallest denomiation not exceeding the remaining sum
4. Dynamic Programming: For each M $\leq$ N, count the optimal way to pay M galleons by considering optimised solutions for M-d, for all d in {25, 15, 1}

This problem is a part of Tessellate S.T.E.M.S.