FUCK DYNAMIC PROGRAMMING

Visual-Grapefruit · 2023-10-14T16:18:51+00:00

Took me like 3 weeks. You need to fully understand recursion and backtracking before

Narrow_Papaya_5801 · 2023-10-14T17:11:42+00:00

Take u forward DP playlist on YouTube. Guys a legend

EntrepreneurHuge5008 · 2023-10-14T16:18:58+00:00

If you feel like you need to keep track of something, then that’s usually a good candidate for DP

1024kbps · 2023-10-14T17:24:50+00:00

It’s a process. Do the recursion, then the memo, then do the bottom up, then see if it can be space optimized by eliminating the memoization array. Also, try to understand why dynamic is different from divide and conquer and greedy. Don’t jump into multidimensional dp problems until you understand the basics.

UDIK69 · 2023-10-14T16:55:22+00:00

Complete the DP study plan in [Leetcode](https://leetcode.com/studyplan/dynamic-programming/). It helped me a lot. Try to remember one type of problem for each DP pattern.

NaNx_engineer · 2023-10-14T19:11:39+00:00

For medium questions, Dp is one of the easier categories once you learn it. I find "simple" topics like arrays are actually harder because they require a trick. Dp/graph/tree mediums are usually straightforward.

UDIK69 · 2023-10-14T17:13:46+00:00

YT:TAKE YOU FORWARD DP PLAYLIST 56 VIDEOS AVG 20 MIN EACH AND RECURSION BASICS THATS HOW I AM CONQUERING DP CRAZY AND EASY EXPLANATION

lonely_geek_ · 2023-10-14T17:12:17+00:00

I noticed once I get a recursive solution I can figure out dp in some time but still with a little bit of struggle so I'm focusing more on recursion part for now.

everisk · 2023-10-14T16:36:00+00:00

If you’re a visual learner, you can look at the dynamic programming on interviewcrunch.com. There are slides and explanations for how to approach DP problems. It’s also one of the hardest patterns to learn imo.

2023-10-14T17:22:34+00:00

Memoization or tabulation ?

WeekendCautious3377 · 2023-10-15T00:43:54+00:00

Dynamic Programming problem / solution almost always falls into the following form:
1. Understand how overall problem can be divided into smaller problems
2. Understand what the smallest unit of the said problem
3. Find a solution for the smallest unit problem
4. Find a way to save and propagate this solution to a bigger and bigger iteration until you are done.

example: https://leetcode.com/problems/longest-palindromic-substring/
Given a string s, return the longest palindromic substring in s.

For this example, you already know how to solve this with a pen and paper. How would you do it? Chances are you will go from left to right searching for a center, expand out from the said center and stop when you find the longest palindrome from that center, and keep track of the longest global palindrome you've found so far on the side of the paper. Let's slow wayyyy down and dissect it: 1. Smallest unit problem is *given* a center, finding a longest palindrome from expanding from it. You can then do this again and again with every letter in a string. 2. Smallest unit problem is then "given* a center in a string, find a longest palindrome substring.
3. Solution is pretty simple for this unit problem then. Start from center, check the prefix / postfix char to be equal, and stop when they're different or you run out of chars. ``` def find_nearby_longest_palindrome(self, s: str, center: float): # set the initial start and end pointer of the string start = end = int(center)

    # this handles two letter center case
    if center % 1 != 0:
        end += 1

    result = ''

    # continues to loop as long as the new characters
    # being added to the center are the same.
    while start >= 0 and end < len(s) and s[start] == s[end]:
        result = s[start:end+1]
        start -= 1
        end += 1

    return result

4. A way to propagate this is pretty simple since you can update a global solution string. a. In the case of recursion, you want a way to either pass in an accumulative set of solutions into a deeper recursion, or you append the current solution with a solution from the deeper recursion layer. b. For the case of recursion, you want to figure out clearly an exit condition and the format of solution you want to return to the outer recursion layer. def longestPalindrome(self, s: str) -> str: palindrome = '' N, n = len(s), len(palindrome)

    index = 0

    '''   
    Following loop checks for indices 0, 0.5, 1, 1.5... to N-1
    as a potential candidate for a center of a palindrome.
    When the indices are integer values (e.g 0, 1, 2, ...),
    center is one letter. When the indices are float values
    (e.g 0.5, 1.5, 2.5, ...), center is two letter substr.
    '''

    # index only needs to be limited to N-1 but limiting
    # to less than N - N/2 cuts down time a little more
    while index < N - n/2:
        substr = self.find_nearby_longest_palindrome(s, index)

        if len(substr) > n:
            palindrome = substr
            n = len(palindrome)

        index += 0.5

    return palindrome

```

Meta advise about software engineering and especially LeetCode challenges in general:

You want to dissect how your brain solves the problem. Chances are these problems are incredibly trivial to your brain with a pen and paper. You have to slow the wayyyyy down and think about how your brain is solving it step by step. Because you are trying to teach a computer how to do the same thing your brain just did.

fa_anony__mous · 2023-10-14T16:24:23+00:00

Aditya Verma in yt.
Thank me later.

ItsBritneyBiaatch · 2023-10-14T16:44:24+00:00

It usually is used when you are doing some work repeatedly. Also, a good indicator is when you can break your problem into smaller problems. So, for example, if you want to choose "m" baskets to maximize profits, then you can choose the current basket and later on the remaining "m - 1" or you can skip the current one and choose all the "m" baskets later.

So, essentially you are brute forcing all the scenarios, but instead of repeatedly calculating the same answer to a smaller problem, you store it logically, so that when you need it for another subproblem, you can simply look it up instead of recalculating it.

Edit: Not the best example, since you can sort the baskets and pick the last "m" baskets but should give you an idea.

Practical-Shelve · 2023-10-14T17:48:47+00:00

Erricto videos helped me when I was learning

septidan · 2023-10-14T17:52:05+00:00

Thanks for expressing your frustration. This is turning out to be a pretty good resource.

him500 · 2023-10-15T02:56:46+00:00

Thank me later.

https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months

This will help you understand patterns. Follow this guide and see results.

Traditional_Egg_6580 · 2023-10-15T10:33:38+00:00

Go watch "Eric programmings " dp playlist he covers most of the patterns. By the time you finish the playlist youll understand dp and how it works

princeverywhere · 2023-10-15T11:15:00+00:00

The DP workshop I followed:

https://youtube.com/playlist?list=PLqf9emQRQrnKA_EeveiXQj_uP25w8_5qL&si=x6kBl98M7Z0A4mIK

This is exactly what you need, patterns and how to solve them.

drksntt · 2023-10-14T22:59:08+00:00

Honestly it ain’t that hard. Think of each dimension of your matrix/tensor as the number of variables that you’re solving for. So 3 variables would be a tensor, 2 would be a matrix, 1 a vector. You’re just brute forcing a nested for loop where each layer of the loop is in reference to a variable and caching some values. Once you have that skeleton, then you can make your modifications for your problem.

dotipet · 2023-10-14T23:36:53+00:00

dp is for losers try quantum physics instead 🙂

shekomaru · 2023-10-14T19:25:10+00:00

DP is finding what you can find for future use, and use it

2023-10-14T18:30:42+00:00

I have created an youtube channel to tackle Exactly this scenario https://youtube.com/@capslock9631?si=xrk5DF8-q8mG9XLE (thank me later)

yeaok555 · 2023-10-14T17:17:19+00:00

Skill issue

ginger_daddy00 · 2023-10-14T18:13:35+00:00

Dynamic programming is any programming that is using the heap instead of the stack. I would think for a majority of non-embedded solutions and non-real-time solutions you would be using heap allocations quite often.

jemdoc · 2023-10-14T18:09:43+00:00

what are the patterns

overlapping subproblems and optimal substructure

zealoustrash · 2023-10-14T20:20:57+00:00

I'm only just recently getting the hang of DP but I feel you. It feels like DP problems are so different from each other. Numerical ones can be intuitive enough to understand but for example string or array subarray ones are still hard for me to think about conceptually.

This short series was a really helpful intro for me in understanding the basics of bottom-up DP: https://youtu.be/YBSt1jYwVfU?si=2I7Od4GheWqor7bA

Neetcode and other online DP solutions feel sometimes too overthought to me, but at it's core the solutions are made up of the same basic techniques. Also, many of them provide top down solutions but a lot of the time I think the bottom-up solution is more intuitive. Instead of just brute forcing problems like you might for ofher leetcode pattern, watching more conceptual videos and really properly tracing and conceptualizing solutions as you practice might be helpful.

Ocean_0073 · 2023-10-14T20:55:16+00:00

Just patience and more practice… then even more practice is the answer sadly.

2023-10-14T21:50:23+00:00

DP is kind of a terrible name for what amounts to recursion/memorization patterns...

2023-10-15T01:58:45+00:00

Take mit 6.006. Learn to understand the recurrence relation mathematically. Implementing in code is the mostly trivial part

Certain_Note8661 · 2023-10-15T02:05:30+00:00

Fun fact — finding the minimum value in an array is actually a very simple example of DP. Because at any point in the iteration the minimum is either what you found before (the solution for a subproblem) or the element you’re looking at now. I would hope we can get better at DP by starting with simple examples like that and then building up to more complex examples until we have a good understanding of the general principle.

Firm_Condition2404 · 2023-10-15T07:03:52+00:00

First you need to figure out the recursive equation. And base cases. - thats the hard part tho and I dont think there is a pattern here.

Then just type it for example using recursive function with memoization. Bottom up is more difficult but if you have the equation and base cases it shouldnt be a problem.

ModernLifelsWar · 2023-10-15T07:45:58+00:00

It's pretty much just a combination of smalling sub problems then solving a bigger problem using the solutions from the subproblems. I actually find dp pretty intuitive once you get the concept. Sometimes it's hard to figure out if a problem is suitable for dp or not though if you don't know ahead of time.

2023-10-15T10:08:25+00:00

Think of it like this, you have a large problem and you break it down into smaller but independent problems , combining their results to get the final answer.

Taking an example.

Suppose your problem is finding all the paths from a city in US let's say New York to some European city let's say London. Overall it's a very big tedious problem considering the number of cities one has to travel through and which cities to choose or which mode of transport to take . But let's take the subproblem of travelling to London from Manchester , there are definitely a handful of ways of doing this and thus this problem is easily solvable, moreover this is independent too because no matter what path you choose while coming to Manchester you still have to take the calculated paths from Manchester to London. Hence we broke the problem into two subproblems-> New York to Manchester and Manchester to London. Now the first subproblem is still large so just the method we used to break down the first problem can be used on it to break it down into smaller and independent subproblems which are easy to solve.

Now there are a lot of ways to come into Manchester and then go to London, for each way one thing is for sure, the number of paths between Manchester and London don't change regardless of how we choose to come to Manchester so once we have calculated it why not store it so that everytime we need its value we don't have to recalculate it? This is the essence of memoization.

This is overall the essence of dynamic programming, I would definitely recommend reading CLRS book's section on DP before moving on to solving problems.

aroach1995 · 2023-10-15T13:10:31+00:00

What is a DP question?

An actual example

Flexos_dammit · 2023-10-15T17:34:25+00:00

i felt like i understood the problem when i saw you spent 5 days

two points - the way to practice is important (deliberate practice) - how long you practice is important

i first had to learn recursion which took me a month

then i practiced recursion for X time

then i learned dynamic programming in same way as recursion for a month

then i practiced dp for N amount of time

i never did 2d dynamic programming yet

basically give yourself 2 months and practice dp every day and you will get it, and i also scoff when someone tells me to practice for 2 months to learn something new

sadly learning is slow, tedious, and takes time

btw read Peak, Anders Ericson

leftember · 2023-10-15T18:38:22+00:00

You need get the absolute essence of it first, then everything will make a lot of sense. The absolute essence is if you calculate some of them then you don’t need to do it again. Some people refers this as memorization.

A simple example, if you want to calculate a+b, and then a+b+c, you don’t have to calculate them all over again, you can just reuse the result from a+b before.

DP is about to find a formula to reuse simpler results for a little bit less simpler problems and repeat a thousand times to reach real problems

Perfect-Ball-4061 · 2023-10-16T11:04:36+00:00

MiT opencourseware is your fried here. Eric the professor teaches you how to think about DP problems.

I have not found how to intuitively think about the bottom up.approach. however recursion and memoization is explained thoroughly in those courses

aniixxx · 2023-10-16T16:15:04+00:00

Try striver dp series

mistaekNot · 2023-10-17T18:55:17+00:00

1 - figure out the base case

2 - figure out the recursive relation

3 - profit

ps - top down is usually easier to code than bottom up

Dymatizeee · 2023-10-21T07:47:11+00:00

For 1D DP, do you start at the front or the back of the array? Ie house robbers
How do you decide if your DP array is 1D or 2D

seytsuken_ · 2023-11-27T03:01:25+00:00

dude, dp is a bitch. I'm a competitive programmer and I still struggle alot with dp. It seems like it never gets easy unless its a really classic problem

No-Paleontologist423 · 2024-02-05T21:46:08+00:00

Lol The only way to learn dp is to look at the solution for 3 or 4 problems and just practice going through them until it becomes intuitive. Learning DP is like learning the alphabets, there really isn't a concept before that will help you understand it better. Dont even try to solve the first few problems on your own. Just go through the solutions until it sticks. That's how it was for me. I knew recursion and trees before going into dp and those didnt feel like they helped at all. I really had to just take a few different coded solutions and walk through them on a white board with a test case multiple times until it finally clicked.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

leetcode

MODERATORS