Brute force algorithm:-
Brute force implies using the definition to solve the problem in a straightforward manner.This kind of problem is same as divide and conquer, except, here we are decreasing the problem in each iteration by a constant size instead of constant factor.
Dynamic programming:-
The word 'dynamic' refers to the method in which the algorithm computes the result. Sometimes, a solution
Here, we are trading space for time. i.e. - we are using more space to hold the computed values to increase the execution speed drastically.
A good example for a problem that has overlapping sub-problem is the relation for Nth Fibonacci number.
It is defined as F(n)= F(n-1) + F (n-2) .
For many problems, making greedy choices leads to an optimal solution. These algorithms are applicable to
For ex- consider the problem where you are given coins of certain denomination and asked to construct certain amount of money in inimum number of coins.
Let the coins be of 1, 5, 10, 20 cents
If we want change for 36 cents, we select the largest possible coin first (greedy choice).
According to this process, we select the coins as follows-
20
20 + 10
20 + 10 + 5
20 + 10 + 5 + 1 = 36.
For coins of given denomination, the greedy algorithm always works.
But in general this is not true.
Consider the denomination as 1, 3, 4 cents
To make 6 cents, according to greedy algorithm the selected coins are 4 + 1 + 1
But, the minimum coins needed are only 2 (3 + 3)
Hence, greedy algorithm is not the correct approach to solve the 'change making' problem.
Infact, we can use dynamic programming to arrive at optimal solution to this problem.
Sometimes it is very hard or not so apparent as to how to arrive at a solution for a particular problem.
In this case, it is easier to transform the problem into something that we recognize, and then try to solve that Instead, we can find the GCD of the problem using a very fast algorithm known as Euclid's algorithm and then use that result to find the LCM as LCM ( a , b ) = (a * b) / GCD ( a , b )
Ex- for an 8 X 8 chess board, if we follow brute force approach, we have to generate 4,426,165,368 solutions and test each of them. Whereas, in backtracking approach, it gets reduced to 40,320 solutions.
