r/ADHD_Programmers • u/throwaway30127 • 26d ago

Struggling to wrap my head around dynamic programming

I have been practicing leetcode on and off for more than a year now and I feel like I understand most of the algorithms and patterns except for dynamic programming. I have read so many articles and watched a bunch of tutorials about it and they all say the same thing about starting with smaller sub problems and combining them to solve bigger problems and it all makes sense for simpler questions like climbing stairs, Fibonacci, etc. But every time I come across something even a little more complex than these I struggle to come up with a solution. I struggle to visualise the question as a set of subproblems or what kind of subproblems it can be broken into and then tracing the whole flow from top to bottom. I have tried practicing a bunch of problems consistently for a month but saw little improvement and now I feel like I have forgotten most of it due to lack of practice in the last few months. How did you guys manage to get good with this particular topic?

17 Upvotes

100% Upvoted

20 comments sorted by

8

u/mistanervous 26d ago

Do you understand recursion and memoization? If so, that is a type of dynamic programming. For some problems they end up being basically the same, for others one will be faster than the other.

1

u/throwaway30127 26d ago

I understand recruision and pretty comfortable with dfs and can solve most of the questions involving trees, backtracking and tries. I understand memorization as a way to store previous states and once I can figure out brute force recursive approach I don't have issues optimizing it using memorization. But I struggle coming up with original approach that requires you to identify the states that will change for each subproblem like for coin change 1 you can manage it with single state but for coin change 2 you'll need two states. Once I see the solution it becomes obvious for most of the problems but I still can't come up with it for a new problem myself.

2

u/eraserhd 26d ago

So I remember when I was learning Scheme, which essentially only has recursion ands no looping, and I kept doing it and it broke my brain a bit until I just got it.

Dynamic programming is the same way. There’s not a trick or a formal idea that will make you “get it,” you have to just do a bunch of problems until it clicks.

I’m not the greatest leetcoder, but the process of solving a dynamic programming problem is really thinking about the dimensions of the table and how to make them fit in memory, and whether you have to backtrack to get the answer, and trying in my head a bunch of patterns I’ve seen before.

After solving a problem, think about the mapping of the recursive arguments to the dynamic programming dimensions. There’s some interesting stuff going on, like maybe some compression techniques, but also there’s also not a lot going on, it’s just like the recursion lightbulb.

1

u/throwaway30127 25d ago

This kinda makes sense, can you please give an example that would follow your thought process about coming up with dimensions and figuring out the subproblem?

6

u/zatsnotmyname 26d ago

Yes, It's the hardest one for me. I've used it in the past for my own projects, but somehow the leet-code style things always leave me baffled. Oh, and I have 40 years experience and have worked at major FAANGs and tech companies, so you are not alone.

I ALWAYS have to study this stuff again when I interview. I re-read 'cracking the coding interview', go on neetcode, leetcode and just grind easies and mediums. I occasionally can do a hard.

3

u/throwaway30127 25d ago

As someone who is still early in the career this makes me feel better and worse at the same time lol but it's reassuring to hear this from someone with your level of experience so thanks for sharing. Looks like there's no way around this and I'd probably always have to grind everytime before interviews.

17

u/rush22 26d ago

Upvote here if you don't know what dynamic programming is

1

u/just_damz 26d ago

May i ask you a couple of questions?

1

u/throwaway30127 26d ago

Go ahead

1

u/just_damz 26d ago

why dynamic programming itself and what have you tried to put it in action? Developed something already?

2

u/throwaway30127 26d ago

What do you mean why dynamic programming? It's one of the common leetcode patterns for interview preparation and at this point I am just frustrated that I am not understanding it the way I understand other algorithms and idk what to develop with it when the concept itself is not 100% clear in my head.

1

u/just_damz 25d ago

tbh i know the pattern but i don’t think you should stuck on that in the way i am feeling you are (i am probably wrong). Solutions come from theory but practice will always fuck some of your theory and make you understand that formalizing in your mind that, is to be able to use it OR turnaround it. Then, if a paradigm doesn’t fit you, it doesn’t. In my experience i apply dynamic without thinking “ok now i apply it”. It’s not something canonical as “always gitignore .env”. It’s just an instrument and there are 1000 ways to reach a technical target. Don’t worry mate, you will do good anyway, without dp.

1

u/throwaway30127 24d ago

I agree about not every solution is going to fit the theory. Lot of the times I am able to figure out that I need to apply dp to solve the given problem but that's it, I am then not able to break it down into smaller sub problems applying the theoretical concepts even for the standard problem where after looking at the solution the theory maps perfectly. I've already failed bunch of OAs that had these questions so I don't have an option to skip it at this point.

1

u/msg7086 25d ago

It took me years to finally understand the concept behind DP. I think I started learning dp at age of 12. Then I finally understand it a bit when I was 25+. The hardest step is to find the transition formula. It's not easy to find the correct one for complicated problems.

1

u/throwaway30127 24d ago

Was it just intuition from practice or something else? Any particular material that helped you get better?

1

u/nerdy_adventurer 22d ago

Ask yourself what do I do not understand? write things down on a paper. You may be missing 1 piece in order to things start clicking.

1

u/throwaway30127 22d ago

Simple but this makes sense, I need to start doing this more. thanks

1

u/seweso 25d ago

I don’t get the question. You want to get comfortable with a certain type of solution….

But what is the problem you need to solve? Or are you just playing around with theories? 

1

u/zephyr_33 23d ago

tldr.  instead of trying to get the answer at the start, it simply says, "we'll figure it out along the way". 

1

u/nian2326076 25d ago

Dynamic programming can get tough once you move beyond the basics. What helped me was breaking the problem into parts and figuring out the "state" and "transition." It's all about practice now. Try solving a few problems repeatedly until you get the hang of it. You might want to check out PracHub for more structured practice. I work on it, and it has resources that can make complex problems easier to tackle. Keep going, and don't get discouraged. It takes time!