algorithms-and-data-structures/AlgorithmsAndDataStructures/Algorithms/DynamicProgramming/UniqueChangeMakingProblem.cs at master · arst/algorithms-and-data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace AlgorithmsAndDataStructures.Algorithms.DynamicProgramming;

public class UniqueChangeMakingProblem
{
#pragma warning disable CA1822 // Mark members as static
    public int GetTotalNumberOfPossibleExchanges(int[] coins, int value)
#pragma warning restore CA1822 // Mark members as static
    {
        if (coins is null) return default;

        var dp = new int[coins.Length + 1][];

        for (var i = 0; i < dp.Length; i++)
        {
            dp[i] = new int[value + 1];
            dp[i][0] = 1;
        }

        for (var currentCoinsAvailable = 1; currentCoinsAvailable < dp.Length; currentCoinsAvailable++)
        for (var currentAmount = 1; currentAmount < dp[currentCoinsAvailable].Length; currentAmount++)
            dp[currentCoinsAvailable][currentAmount] = dp[currentCoinsAvailable - 1][currentAmount]
                                                       + (currentAmount - coins[currentCoinsAvailable - 1] >= 0
                                                           ? dp[currentCoinsAvailable][
                                                               currentAmount - coins[currentCoinsAvailable - 1]]
                                                           : 0);

        return dp[coins.Length][value];
    }
}