How to solve dp related problems?

I understood the concept of dynamic programming,but i was unable to solve problems on online judge.
Any one please tell is there any proper approach to prepare dynamic programming and how to identify the subproblems.

For example:http://morris821028.github.io/2014/08/02/oj/uva/uva-12283/
A dp solution how to identify sub problem for such kind of problems

2 Likes

Hi pallesai,

when the question is about dp then there is not any exact method to identify the subproblems its all depend upon your practice there are various dp standard problem and in order to solve question you have to map that problem according to dp standard problem, means for solving question logic will be same but there will be some difference according to question. finally you have to identify which dp standard problem is related to your question.

eg in june15 the problem MCHEF includes knapsack dp problem.

there are various problem :- knapsack problem ,subset sum problem,rod cutting problem,longest common subsequence etc.
but if you wanna solve question apart from these then you have to do everything cracking logic ,identifying subproblems and implementing :slight_smile: i hope it would not hurt you because it is the truth about dp. practice practice practice :frowning:

5 Likes

just solve problem by bruteforce and then
anlyze are subproblem overlapping then store ans of already solved subproblem and use further to solve next subprolem…

*** that’s why dp also called carefully implemented bruteforce***

happy coding…

1 Like

the link you have given is in chinese language.