dumbguy's blog

Dynamic Programming!!!
By dumbguy, history, 7 years ago, In English

Hello guys,
I am facing difficulties solving DP problems. It's like i am not able to do even the easy ones.
I know some classical problems and have even solved other problems on DP but i am not improving i guess.
I don't get to the correct DP states even after thinking for a while.
Any advice would be appreciated. Thanks.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Open Problemset, select DP tag, Sort by Solved, Think on every problem 90 minutes, If you couldn't Solve it, Read tutorial.

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think Dynamic Programming is really a quite difficult topic (at least for me). Sometimes it is really tough to figure out how to construct correct states and deduce the recursive formula. Perhaps this it not like solving an equation, for instance, ax2 + bx + c = 0, which we have some "systematic" steps to follow. Well, it seems that DP is more related with "intuitive understanding"...

I think you can start with some classical DP problems, such as backpack problem, Pascal's triangle, and so on. Next, you should keep practicing and solving new problems, and as you practice more, you will get some more clear understanding about this technique.

As for me, at first I could not understand bit-mask DP at all, however after I solved several problems (follow tutorials), I found that I could also handle some simple bit-mask DP problems. I think most of the master coders also suffered a lot when they started learning new techniques. Sometimes perhaps we only see their success, but do not realize that they have also worked quite hard. Believe yourself :D

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Practice makes perfect.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try solving problems of mathematical induction. And learn induction if you don't know already :)

→ Reply