To apply the dynamic programming algorithm to solve the change-making problem for the denominations 1, 3, 5 and the amount n = 9 using a bottom-up approach.

Here are the steps as follows:

1. Create an array dp of size (n+1) and initialize all elements to infinity except dp[0] = 0, where n is the desired amount. This array will store the minimum number of coins needed to make change for each amount from 0 to n.

2. For each coin denomination, iterate from the smallest denomination to the largest denomination:

   • For i from denomination to n:
     • Update dp[i] as the minimum of dp[i] and dp[i - denomination] + 1. This step ensures that we consider all possible combinations of coins to find the minimum number of coins required.

3. The value in dp[n] will represent the minimum number of coins needed to make change for the amount n.

4. To find the actual coins used, we can backtrack through the dp array:

   • Initialize a variable amount = n.

   • Initialize an empty array result[] to store the coins used.

   • While amount > 0:

     • For each coin denomination in reverse order:
       • If dp[amount] = dp[amount - denomination] + 1, add the denomination to the result[] array and update amount = amount - denomination.

   • The result[] array will contain the coins used to make change for the amount n.

Let's apply these steps to find all the solutions to the change-making problem for the denominations 1, 3, 5 and the amount n = 9:

1. Create the dp array: dp = [∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] dp[0] = 0

2. Iterate through each denomination:

   • For denomination = 1:

     • For i from 1 to 9:
       • Update dp[i] = min(dp[i], dp[i - 1] + 1) (dp[1] = min(∞, ∞ + 1) = 1, dp[2] = min(∞, ∞ + 1) = 1, ..., dp[9] = min(∞, ∞ + 1) = 1)

   • For denomination = 3:

     • For i from 3 to 9:
       • Update dp[i] = min(dp[i], dp[i - 3] + 1) (dp[3] = min(1, ∞ + 1) = 1, dp[4] = min(1, ∞ + 1) = 1, ..., dp[9] = min(1, ∞ + 1) = 1)

   • For denomination = 5:

     • For i from 5 to 9:
       • Update dp[i] = min(dp[i], dp[i - 5] + 1) (dp[5] = min(1, ∞ + 1) = 1, dp[6] = min(1, ∞ + 1) = 1, ..., dp[9] = min(1, 1 + 1) = 1)

3. The value in dp[9] = 1 represents the minimum number of coins needed to make change for the amount 9.

4. To find the coins used, backtrack through the dp array:

   • Set amount = 9.

   • Initialize an empty array result[].

   • While amount > 0:

     • For each coin denomination in reverse order (5, 3, 1):
       • If dp[amount] = dp[amount - denomination] + 1, add the denomination to the result[] array and update amount = amount - denomination. (At each step, add the coin used to the result[] array and subtract its value from the amount.)

   • The result[] array will contain the coins used to make change for the amount 9. (In this case, result[] = [5, 1, 1, 1, 1])

Hence, for the denominations 1, 3, 5 and the amount n = 9, the minimum number of coins required to make change is 1, and the coins used are [5, 1, 1, 1, 1].