GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
176 views

Could someone tell me What is the general idea to approach to problems in Dynamic Programming ?

ie. Given a problem How do I start my thinking :P , Im not getting a clue to deal with DP problems .  Making Recursive Equations etc .

Is DP approach is suitable for any problems ?

---------------------------------------------------------------------------------------------------------------------------------------------------

Example Problem

Min-Coin Change is the problem of using the minimum number of coins to make change for a particular amount of cents, n, using a given set of denominations d_{1}\ldots d_{m}.

Given the denominations 1, 5, 10, 20, 25, and wish to make change for 40 cents, the greedy algorithm would give us 25, 10, 5, but the best solution only requires 2 coins - 2 of the 20 cent coins

asked in Algorithms by Loyal (2.7k points)   | 176 views

if you really want more general idea about DP ..you better search competitive programming problems on others sites and their different solution methods. 

These will be useful ...coin change is there in the first pdf.

pdf1

pdf2

pdf3

By examples we get some idea of DP.
mean >?
like we cannot define it directly.

but examining floyd warshall, bellman ford, knapsack we can understand how it works.

Like a small problem able to solve a big problem.

mostly like fibonacci numbers

I just wanted to know a general method to wrte recursion equation .
See here http://gateoverflow.in/8399/gate2015-3_5

I didn't understand how he managed to get the cell  (i)(j)

2 Answers

+1 vote
Given a problem , you have to first check whether you can apply dynamic programming in it . In order to apply the dynamic programming paradigm in a problem, the problem must have an optimal substructure and overlapping subproblems . These are the basic prerequisites for DP which you can find in any book. But what these actually mean is that the answer to the problem can only be computed once you find the answer to its subproblems or else you won't get an optimal answer to the larger problem unlike that in a greedy solution oriented problem where you can directly compute the answer to the problem.

A very important idea of approach in DP problems is that it stores all the answers to the subproblems that it once computed and it never computes the same subproblem twice thus reducing the time complexity to a great extent unlike that in divide and conquer approach where we repeatedly solve the same subproblems if they are not unique and increase the time complexity.

The coin change problem is a classical DP problem because the higher denominations depend on the lower denominations and the solution can be developed starting from the lowest denomination.

Thus DP problems always follow the golden rule that the optimal answer to the smaller subproblems leads to the optimal answer to the larger problem. If you can directly find the answer to the problem without finding the answer to its self similar subproblems then it is not a dynamic programming solution.
answered by (153 points)  
+1 vote

well, it is very good to understand the concept and then apply and I hope you must be aware of DP clearly, the fact that how to recognize whether we have to apply DP or not comes with practice of questions.

Some of the questions will really create the illusion...nd you get confused so it's better to start like...

firstly go with basics of DP and compare with the problem, i.e in any way we can store and use the results kind of situation or not.

second thing there are some classic problems of DP which you must remember because many time questions are based on the classic problem with modification...like the above question is similar to the sum of subset.

answered by Active (1.1k points)  

Related questions



Top Users Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,348 comments
31,011 users