Aur Chinti Phad chad jaati haii ...
Bekar Tukbandi ...
But dynamic programming is something like that.
By definition Dynamic programming is : To solve a Problem use Sub-problem's solution.
Most familiar problem most of us have already programmed is Prime number Generation Or Fibonacci.
Prob: print all prime numbers upto N.
And the solution will be ...
printPrime(int N){
int i,j;
for( i=2; i < N ;i++){
for( j=2; j < i ; j++) {
if(i%j == 0) break;
}
if(j==i-1)
cout<< j << " ";
}
}
something like that. Time requires is O(N*N) :(
Worst/naive solution.
On doing some analysis, we can easily prove that if number m is not divisible by primes up to m, then it will be a prime number. So if we have stored the primes we have find till i < m then very few iterations require in comparison to N. Which will give you a great improvement over O(n*n);
The change requires to use previously find solution for the next solution(i.e. for checking next prime number). AND a little analysis.
Aaj aapko DP ki definition pata hai ..
Kya Aap log santust ho ..
kya kha nahii...
Banna chahoge duniya ke sabse bade programmer
Tau phir hum ek aur DP problem open kare...
[thoda jayada ho gya, I cant do it. But still can try to be.]
Other Easy Problem is:
We need to find minimum number of coins required for finding sum S, using {c1, c2, c3, c4}, set of coins. Any coin can be used any number of times.
SOLUTION:
Dynamic Programming.........................
huh!
How could you say it? :?
That's the actual confusion which inspires me to write this post. If, I am navigating Dynamic Problem(DP) category, then we can say oh! that Problem will be solved using DP. But for now how can we find that its a DP prob.
The approach, I followed( must say observed)
0. UNDERSTAND PROBLEM CORRECTLY.
[ One of the problem area for difficult problem, because me too not spend actual required time for it]
1. How to solve the problem without using any Store (or say in the Generic manner).
[Every solvable problem can be solved by analyzing all the possible combination. And find the required best solution out of them].
If someone have created Quantum Computer in the stone age, Algo & DS don't required to be added in the CS stream course syllabus.
2. Analyze the special points.
[ e.g. In Prime Number Problem we find that divisibility need not to be checked with all the numbers, only Prime numbers divisibility check will be enough to do.]
3. Try to minimize solution using this Analysis.
[ Some early analysis, I have missed in the Prime Number Problem because Post is about DP.
Like, only sqrt(N) inner iterations will be enough,
and, iterate with the increment of 2 in the inner iterations.]
4. Cry!!!! oh shit!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Its to much time taking.
5. ASK to the problem, if old solutions will be helpful to find final solution faster.
[like in prime number problem Last prime number will be found too early if we have all prime number primes upto N]
6. Prepare required store. Use the store to minimize time.
7. Wakauuuuuuuuu!!!!!!!!!!!!
done dona done done.
My observation and Definitions to....
1. May be you will find that normally all the solutions are dumped to linear from recursive.
2. ---- As I will found other, I will put it here ---------------
Now Coin problem using these steps:
Step 0:
So problem is to find the number of coins only. Not the actual combination which form the sum S.
Any number of coin can be used of any type. So no limit on count.
Prepare one example.
{4, 5, 7} is coin set. and Sum is 20
Possible solutions are,
5,5,5,5 (ok)
7,5,4,4 (ok)
4,4,4,4,4 (ok)
7, 7,7 (X)
So, I find that on sum of different coins combination (l*C1+m*C2+n*C3) < S.
so problem is to find the different l, m, n values and then minimum l+m+n.
Oh Great!!
Step 1:
Generic Solution:
so, find all combination of l, m, n and see which of them can produce S.
find minimum of l+m+n.
Problem says that any l,m,n can be used BUT, as we have analyzed above "(l*C1+m*C2+n*C3) < S "
so if m=0, n=0 l=S/C1. will be the maximum value. Similarly,
0<= l <=S/C1
0<= m <=S/C2
0<= n <=S/C3
creq=2<<30; //infinite
for(i=0; i<=S/C1+1;i++)
for(j=0; j<=S/C2+1;j++)
for(k=0; k<=S/C2+1;k++)
if(i*C1+j*C2+k*C3 == S)
if(creq > i+j+k)
creq=i+j+k;
{That is on for three coins, but if there are N coins}
But still that also requires exponential time.
I have write some recursive solution for it.
We can find S, if we can find S-C1 or S-C2 or S-C3..
so, pseudo code will be like
fun coinCount(S){
if S< 0
return NOT_POSSIBLE;
if S==0
return 0; //Solution done with zero coin
foreach( COINS, c)
RES[i++]=coinCount(S-c)
return ( 1+minimum(RES) );
}
Do it looks Ok?
some correction may require, but looks Ok base to me.
Step 3:
Time to sleep....
Analyze above logics, we will append it tomorrow.
Thanks
for tolerating top 2 Lines
