The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Dynamic Programming

Problem :-
Coin Change problem.
Given a set of coin denominations, find the minimum number of coins required to make a change
for a target value.
Consider a set of denominations as { 1, 2, 5, 9 }.
Suppose we want to make a change for a target value = 13.

There are many possible ways like using
13 coins of denomination 1 ( Total 13 coins )
6 coins of denomination 2 & 1 coin of denomination 1 ( Total 7 coins )
2 coins of denomination 5 with 1 coin each of denomination 1 & 2 ( Total 4 coins )

Minimum no. of coins = 3 ( 1 coin of denomination 9, 2 coins of denomination 2 )

Solution :-
Suppose we are given an array value [ n ] which stores coins of n denominations.
We will maintain an array change [ n + 1 ] where index j of the array stores the minimum number of coins required to make a change for value j. Eventually, change [ x ] will give the solution ( minimum no. of coins required to make a change for target value x ).
Let us find the structure of the optimal solution.
Let change ( j ) denotes the minimum number of coins required to make a change for value ' j '.
Now, to achieve that, we need to decide whether to consider a coin of particular denomination.
So, we will iterate through the array value [ n ] and either choose or reject a coin. If we choose a coin of denomination i , then the problem reduces to 1 + ( No. of coins to make a change for ' j - value ( i ) ' )
Since, our objective is to find minimum no. of coins required to make a change for value j,
we will consider every possible denomination i ( i = 0, 1, ... n ) and find the
minimum ( 1 + ( No. of coins to make a change for ' j - value ( i ) ' ) ) for all values of ' i '.
Thus, the structure of the optimal solution is defined recursively as :
change ( j ) = min [ ( 1 + change ( j - values [ i ] ) ) for i = 0 , 1 , ... , n ]
change ( x ) is the required solution.