Dynamic Programming - Making Change Problem C Code

Dynamic Programming & making Change :

Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Fortunately, some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are proven to lead to the optimal solution.

For example, in the coin change problem of finding the minimum number of coins of given denominations needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount. In contrast, a greedy algorithm might treat the solution as a sequence of coins, starting from the given amount and at each step subtracting the largest possible coin denomination that is less than the current remaining amount. If the coin denominations are 1,4,5,15,20 and the given amount is 23, this greedy algorithm gives a non-optimal solution of 20+1+1+1, while the optimal solution is 15+4+4..

C Coding for making Change : -

#include<iostream>
#define Infinite 10000
using namespace std;
int main()
{
    cout << "Total Number of COinS : ";
    int noC;
    cin >> noC;
    int Coin[noC];
    for(int i=0;i<noC;i++)
    {
        cout << "Enter Value of " << i+1 << " Coin :";
        cin >> Coin[i];
    }
    cout << "Enter Amount : ";
    int amount ;
    cin >> amount ;
    int dynamicArr[amount+1][noC+1];
    for(int i=0;i<=noC;i++)
    {
        for(int j=0;j<=amount;j++)
        {
            if(j==0)
            {
                dynamicArr[i][j] = 0;
            }
            else if(i==0)
            {
                dynamicArr[i][j] = Infinite;
            }
            else if()

                /*WIll be Uploaded SOon OR Try by urself*/
        }
    }

}