needed help to learn dynamic programming approach

general
1

i want to know how should i begin solving problems involving dynamic programming?.Please suggest some good video tutorial links or references.

1 Like
2

The dynamic programming section of Geek for geeks has a lot of algorithms and codes explained beautifully. You can refer to them (especially first 5) to have a taste of dp.

Videos from Tushar Roy are good, from what I have heard.

Also, you asked how to begin dp problems? First check geekforgeeks and get a taste of how dynamic programming actually is. Then practice some standard Q, like Longest increasing sequence, Contiguous sub-array with maximum sum, SPOJ’s ALTSEQ. Start from very easy Q to develop thinking in terms of dp. Try to analyse the problem. During analysis, ask yourself 2 Q-

  • What are the things that I have to
    compute again and again?
  • How can I use my previous
    computations to help in my next
    computation?

This would atleast hint on the approach you have to take.

Check this out, and tell me if you need more basic Q of dp. When you get more confident, you can do easy and medium category Q easily.

Also- sites like hackerearth.com have a very good section of dp, there are many easy problems to see. But I would say its one level up, so practice the very basic Q first!

3 Likes
3

I would suggest you, go through MIT CS 6006 video lecture, since you’re interested about only DP, go through only DP videos probably there are four of them. Once you are over with that you’ll have an insight into what DP actually is and it’ll help you to think recursively. After that start solving DP problems on codeforces or codechef (sort based on submission and start solving).

DP is nothing but brute force with memoization so you should be thorough with how recursion works, it’ll help you with the thinking process, iterative thinking is tough for beginners, so think recursively first then try to solve iteratively.

Read these links:Link 1, Link 2

Read the DP part by Annudeep Nekkanti : Link 3

1 Like
4

@vijju123

Tushar Roy videos are good…I have learnt basic problems from here only.

5

Yes, that’s a very beautiful explanation you got there!

1 Like
6

I’m following these and progressing bit by bit… :smiley:

1 Like
7

You are already so well versed in dp. Me on other hand :3. I still laugh at that hill number thing I was using…XD

1 Like
8

I’m not well versed with dp, and I too made similar mistake on that problem when I attempted it the first time. :smiley: Making mistake is a way to learn. :smiley:

1 Like
9

True. Making mistakes is how I started learning dp too. :slight_smile:

1 Like
10

True, I also do mistakes but they aren’t silly. :wink:

11

Thanks for affirmation dear :slight_smile: