Dynamic Programming Solution

Now that we have seen the recursive solution to the coin change problem, let's move on to a more efficient approach using dynamic programming.

Dynamic programming is a technique where we solve a complex problem by breaking it down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations. It allows us to solve problems with overlapping subproblems and optimal substructure.

In the case of the coin change problem, we can use dynamic programming to find the minimum number of coins needed to make a given amount of change.

Here's the implementation of the dynamic programming solution in C#:

1{{code}}

In this solution, we create an array dp of size amount + 1 and initialize all its values to amount + 1, except for dp[0] which is set to 0 since we don't need any coins to make zero change.

We then iterate from 1 to amount and for each value i, we iterate through the coins array. If the current coin coin is less than or equal to i, we update dp[i] to be the minimum between its current value and dp[i - coin] + 1. This represents the minimum number of coins needed to make the amount i using the current coin and any previously calculated solutions.

Finally, we return dp[amount], which will be the minimum number of coins needed to make the given amount of change. If dp[amount] is greater than amount, it means that it was not possible to make the amount using the given coins, so we return -1.

Let's run the code and see the output:

1Minimum number of coins needed: 3

xxxxxxxxxx

}

using System;

​

public class CoinChangeSolution

{

    public static int CoinChange(int[] coins, int amount)

    {

        int[] dp = new int[amount + 1];

        Array.Fill(dp, amount + 1);

        dp[0] = 0;

​

        for (int i = 1; i <= amount; i++)

        {

            foreach (int coin in coins)

            {

                if (coin <= i)

                {

                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);

                }

            }

        }

​

        return dp[amount] > amount ? -1 : dp[amount];

    }

​

    public static void Main()

    {

        int[] coins = { 1, 2, 5 };

        int amount = 11;

​