gantavyamalviya's blog

By gantavyamalviya, history, 4 months ago, In English

Howdy Coders,

Most of the newbies have suffer with DP and find it difficult to approach, here i come up with some standard procedure which helped me a lot while solving DP problems, So, I am writing down the procedure here:

1) Identifying the subproblem : This basically means how is your original problem related to a smaller problem but of the same type. Identifying base cases and building up from them also helps.

2) Finding the relation between the problem and subproblem : This is finding out the recursive relation. For this you need to know how the solution of the subproblems should be combined to obtain the solution for the original problem.

3) Deciding a memoization strategy : Decide how you want to store the computed solutions for the subproblems so you can use them for calculating larger problems.

4) Check acyclicity : This means that your problem should not depend on something that is not yet computed, or is to be computed in a later stage.

These are some helpful tips I have learnt from youtubers :

1) Try to do it greedily, if it doesn't work then there are high chances its a DP problem.

2) Look at the constraints, the constraints give you a good idea about the dimension of the dp. For example : 1<=n<=500, 1<=k<=n so you can see that dp[n][k] is possible. On the other hand if n<=50000 , k<=50000 you can straight away stop thinking about dp[n][k] since the constraints are very high.

3) Solve standard problems and lock the concept in your mind forever. A lot of times dp problems are modifications of standard dp problems ( atleast in my rating range ) and so this helps. {For Example : Coin Change/ Rod Cutting is a type of standard Unbounded Knapsack DP}

4) Practice, Practice and Practice !!!!!!!!!!!

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it