GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
74 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 Active (1.7k points)   | 74 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)

Please log in or register to answer this question.

Related questions

Top Users Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,034 answers
52,724 comments
20,276 users