Scribd
Upload
51 views2 pages

Lets Have A Look at The Following Program Below

The coin change problem is a classic example of dynamic programming. It involves calculating the number of combinations of coins that can be used to make up a given total. For example, with coins of 1, 5, and 10 cents, there are 2 ways to make 8 cents: with all 1 cent coins or with 1 cent and a 5 cent coin. Dynamic programming breaks the problem down into subproblems by iterating through coin values and building up the solution table. The C# program demonstrates calculating the number of combinations for any given total using this dynamic programming approach.

Uploaded by

VETTRIRAAM A CSE2019
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
51 views2 pages

Lets Have A Look at The Following Program Below

The coin change problem is a classic example of dynamic programming. It involves calculating the number of combinations of coins that can be used to make up a given total. For example, with coins of 1, 5, and 10 cents, there are 2 ways to make 8 cents: with all 1 cent coins or with 1 cent and a 5 cent coin. Dynamic programming breaks the problem down into subproblems by iterating through coin values and building up the solution table. The C# program demonstrates calculating the number of combinations for any given total using this dynamic programming approach.

Uploaded by

VETTRIRAAM A CSE2019
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

The 

Coin Change Problem is considered by many to be essential to understanding the


paradigm of programming known as Dynamic Programming. The two often are always
paired together because the coin change problem encompass the concepts of dynamic
programming. In other words, dynamic problem is a method of programming that is used to
simplify a problem into smaller pieces. For example if you were asked simply what is 3 *
89? you perhaps would not know the answer off of your head as you probably know what
is 2 * 2. However, if you knew what was 3 * 88 (264) then certainly you can deduce 3 * 89.
All you would have to do is add 3 to the previous multiple and you would arrive at the
answer of 267. Thus, that is a very simple explanation of what is dynamic programming
and perhaps you can now see how it can be used to solve large time complexity problems
effectively.
By keeping the above definition of dynamic programming in mind, we can now move
forward to the Coin Change Problem

Example 1: Suppose you are given the coins 1 cent, 5 cents, and 10 cents with N = 8
cents, what are the total number of combinations of the coins you can arrange to obtain 8
cents. 
Input: N=8
Coins : 1, 5, 10
Output: 2
Explanation:
1 way:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 cents.
2 way:
1 + 1 + 1 + 5 = 8 cents.

lets have a look at the following program below:


using System;
 
public class getWays
{
 
    static long getNumberOfWays(long N, long[] Coins)
    {
        // Create the ways array to 1 plus the amount
        // to stop overflow
        long[] ways = new long[(int)N + 1];
 
        // Set the first way to 1 because its 0 and
        // there is 1 way to make 0 with 0 coins
        ways[0] = 1;
 
        // Go through all of the coins
        for (int i = 0; i < Coins.Length; i++)
        {
 
            // Make a comparison to each index value
            // of ways with the coin value.
            for (int j = 0; j < ways.Length; j++)
            {
                if (Coins[i] <= j)
                {
     
                    // Update the ways array
                    ways[j] += ways[(int)(j - Coins[i])];
                }
            }
        }
 
        // return the value at the Nth position
        // of the ways array.
        return ways[(int)N];
    }
 
    static void printArray(long[] coins)
    {
        foreach (long i in coins)
            Console.WriteLine(i);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        long []Coins = { 1, 5, 10 };
 
        Console.WriteLine("The Coins Array:");
        printArray(Coins);
 
        Console.WriteLine("Solution:");
        Console.WriteLine(getNumberOfWays(12, Coins));
    }
}

You might also like