Problem Description

In this problem, you are given a set of coin denominations and an amount of money. Your task is to determine the minimum number of coins required to make up that amount using the available coin denominations. There are no limitations on the number of coins you can use for each denomination.

Input Format:

• The first line contains two integers: the target amount and the size of the coin set.
• The second line lists the coin denominations available, separated by spaces.

Output Format:

• The output should list the number of each coin denomination used to make up the target amount, minimizing the total number of coins. If it's impossible to make the exact amount with the given coin denominations, the output should indicate that no solution exists.

Function Implementation:

The core logic is implemented in the NoLimitsDynamic method, which accepts the target amount and the array of coin denominations. It outputs an array indicating the number of coins used for each denomination.

This method utilizes dynamic programming to compute the minimum number of coins required for each amount up to the target. It also keeps track of the last coin used for each amount to reconstruct the solution.

Remarks:

• The coins[i] parameter represents the denomination of the i-th coin type.
• The change[i] output array represents the number of coins of the i-th denomination used in the solution.
• If it's impossible to make the exact target amount with the given coin denominations, both the change array and the method's return value will be null.
• The auxiliary memory used by the method should be proportional to the target amount, i.e., O(amount), ensuring efficiency in terms of space complexity.

Example Inputs and Outputs

Example 1:

Input:

23 1
1

Output:

23

Explanation: The target amount is 23, and there is only one coin denomination available, which is 1. Therefore, 23 coins of denomination 1 are required to make up the amount.

Example 2:

Input:

123 8
1 2 5 10 20 50 100 200

Output:

1 1 0 0 1 0 1 0

Explanation: The target amount is 123, and the available denominations are 1, 2, 5, 10, 20, 50, 100, and 200. The optimal solution uses 1 coin of denomination 1, 1 coin of denomination 2, 1 coin of denomination 20, and 1 coin of denomination 100, making a total of 4 coins.

Example 3:

Input:

123 7
2 5 10 20 50 100 200

Output:

4 1 1 0 0 1 0

Explanation: The target amount is 123, but the coin of denomination 1 is not available. The optimal solution is to use 4 coins of denomination 2, 1 coin of denomination 5, 1 coin of denomination 10, and 1 coin of denomination 100, totaling 7 coins.

Example 4:

Input:

23 1
2

Output:

null

Explanation: The target amount is 23, but the only available denomination is 2. It is impossible to make up the amount 23 using only coins of denomination 2, so the output is null.

Example 5:

Input:

23 1
50

Output:

null

Explanation: The target amount is 23, but the only available denomination is 50. Since 50 is greater than 23, it's impossible to make up the amount, resulting in a null output.

These examples illustrate how the problem and its solution adapt to different sets of coin denominations and target amounts, showcasing the application of dynamic programming to achieve an optimal solution in terms of the minimum number of coins required.