How do you approach hard leetcode problems ?
In particular DP problems Any good sources for learning to solve DP problems ? TC: 170k
I just don’t approach them at all
Draw lots of pictures, then go through the test cases slowly to understand exactly what is going on with each step and each branch of logic. You should be able to see some kind of repeating pattern. In general, I find bottom-up much more intuitive than top-down.
Yeah pen and paper is the best way to approach non-trivial dp problems. I also start with recursion. Once you see the recursive relation, it's a little easier to transform that to dp.
I think of an exponential time recursion to solve the problem and then see what duplicate computations I can cache.
Come up with exponential recursion or backtracking solutions. Write down the recursion tree see duplicates and optimize. The best thing I found to learn new paradigms is to talk and discuss the problem with people. In a 30 mins discussion with ur friends I would have discovered 5-6 ways to solve a problem
It took me an embarrassingly long time to “get” DP problems. What helped me was to find a dozen algorithm textbooks and read each of their DP sections. I forced myself to close my eyes and visualize the table filling for each of the problems presented. Some problems like the matrix multiplication solution took me multiple days to finally visualize it completely. Now, my brain is much more used to table filling and recognizing how sub problems fit together.
can you solve a random DP on leetcode?
Can you share resources to study? Also, what's embarrassingly long lol