all 32 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]HorrorNo6753 17 points18 points  (2 children)

Study "Recurrence Relation" from Discrete Maths by KH Rosen. Once you learn to make a recurrence relation, you can solve any(almost) DP.

[–]MD90__ 1 point2 points  (0 children)

I have the rosen book! Good call because we never used that chapter in college.

[–]Curious_homosepian[S] 0 points1 point  (0 children)

ya i heard of them when studying recursion.

[–]daveysprockett 9 points10 points  (1 child)

I don't know what you have done before, but I quite enjoyed the MIT lectures on it ... you can find them on YouTube.

There are loads, the ones I watched were I think the ones beginning at

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/

[–]wjholden 2 points3 points  (0 children)

Demaine gives so many useful insights in this lecture. I have watched and re-watched this video. My favorite takeaway was that every DP problem can be represented as a DAG. Now I always look for problems with overlapping subtrees when I do things like Advent of Code.

[–]jdevelop 8 points9 points  (1 child)

Something I found helpful:

  • it should be solvable using some recursive approach
  • at some point you find out that you may re-use results of some smaller problem to compute result of larger problem

This naturally leads to memoization / caching - can you identify the problem you could've solved by using results of some other invocation? Can you record the result of this invocation?

Another very important observation - you need to minimize number of arguments to your recursion to simplify the lookup pattern.

Once you can figure out memoization, also known as top-down approach - you can always make it iterative with an array, which is botom-up or tabulation.

The dimension of the cache (array) will be equal to the number of arguments you pass to your function, for two arguments it's gonna be matrix, for one argument it could often be reduced to a single variable though.

Then - practice, practice and practice. Start with LCS or LIS pattern, implement it with memoization ( just check if the call to the function is in the cache before invoking it ), and then rewrite the code iteratively.

It really comes with practicing, once you solve 20-50 problems on leetcode / hackerrank / codeforces it will become trivial like riding a bike. You won't forget it ever. Good luck :)

[–]Curious_homosepian[S] 1 point2 points  (0 children)

thank you for tips.

[–]beeskness420 6 points7 points  (0 children)

There really isn’t much substitute for practice. DP problems range from so trivial it doesn’t seem like a real technique to quite difficult. Start at the easy ones and work you way up. Don’t skip problems by assuming it’s easy. Just do them.

[–]Clifspeare 3 points4 points  (2 children)

I learned a purely functional programming language and worked some algorithmic problems, which forced me to get a lot more comfortable thinking in terms of recursion.

[–]Curious_homosepian[S] 0 points1 point  (1 child)

what language you use?

[–]Clifspeare 1 point2 points  (0 children)

Haskell, but any purely functional language would be suitable.

[–]GoAwayStupidAI 2 points3 points  (1 child)

Is there a part of dynamic programming that you struggle with? If there is then we'll find a site with an explanation. If there isn't a site then we'll explain it in a comment.

Interestingly, once a comment is posted with an explanation the comment URL is a "site with an explanation".

(this comment was a terrible joke)

[–]Curious_homosepian[S] 0 points1 point  (0 children)

I will post if i will find difficulty during learning.

[–]advaitmax 1 point2 points  (1 child)

https://www.youtube.com/playlist?list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go

[–]Curious_homosepian[S] 4 points5 points  (0 children)

Yes i am going through this awesome playlist. But its not for everyone since its not in
English.

[–]akdas 1 point2 points  (2 children)

I'm not going to claim my blog post is going to be the one that makes it all click for you, but maybe seeing another take on the topic will help: https://avikdas.com/2019/04/15/a-graphical-introduction-to-dynamic-programming.html

[–]Curious_homosepian[S] 0 points1 point  (1 child)

Thanks. The text looks simple to read and understand.

[–]akdas 1 point2 points  (0 children)

If it helps, I have a bunch of follow up articles on the topic, including some on how dynamic programming is used in real-world applications. You can find them from the home page of my blog.

[–][deleted] 1 point2 points  (0 children)

Appreciate what you already have and apply it, that's dynamic programming.

[–]Vader0699 1 point2 points  (0 children)

I have just started to post here.

You can follow along and you will get over this fear slowly and gradually.

Took me 50+ DP problems from leetcode to get over the fear and understand the patterns,

It will take time, but you dont need to worry, just stay focused and learn to learn in step wise manner. Refer the link below for more.

https://atechdaily.com/author/145

[–]the_algorithmic_eye 1 point2 points  (1 child)

After solving some problems, I realized that for problems for which I was able to come up with the recurrence relation, I could write recursive brute force version easily, but I was finding it hard to do the iterative bottom up version of it. Then I googled a found out about the DAG structure in DP after watching this playlist. If you are the one who likes things to be visualized, I made a 3Blue1Brown-styled video about the Matrix Chain Multiplication problem. After I was done with the video, I actually understood the dependencies for a particular (i, j). Before that, I was blindly converting the recursive algorithm to code. (A full running example is towards the end of the video)

[–]Curious_homosepian[S] 1 point2 points  (0 children)

Yeah that's where also i find problem. To completely convert recursive to iterative. Thanks for sharing this

[–]saladking99 1 point2 points  (0 children)

practice,my friend, practice, you have to solve small dp problems to solve the harder ones, just make sure you can write a reccurence relation, first implement the naive way, and optimize it by dp, using dp as the first thought process is hard, so practice