Take a problem that you could brute force. Does it have repeating sub problems? If so, it's a candidate for DP.

DP and Greedy problems are the hardest to nail because they are the broadest and widest category of problems. Almost everything can be a DP problem.

> i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books, and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help.

I dread at the thought of coming across you in an interview loop some day.

You dread the thought of coming across someone who mastered a challenging technique? Ok

Yeah, when the challenge is dynamic programing and the goal is a FAANG job.

I don't mean it as a put down, but it is a realization of my own how much the field has moved on since the last time I applied for a programer job.

fwiw I don't ask dp questions on interviews and most of FB doesn't either (I didn't know that before I got hired)

brute force recursive solution + @lru_cache annotation.

works for me every time on leetcode.

everyone always says this as if it's some kind of galaxy brain epiphany. it's not because

1) on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier

2) you can easily blow the stack for real production grade implementations using recursion (think edit distance for genome sequences). you also lose time actually doing the recursion. on the other hand, it's easier to prune the search space with explicit recursion vs tabulation.

edit: btw i'll also say that dynamic programming proper, i.e. as a technique for solving optimization problems defined by recurrence relations, uses tables and recursion (fixed points). so good luck understanding something like the linear quadratic regulator if you think it's just @lru_cache

https://berkeley-me233.github.io/static/ME233_Sp16_L1_DP_Opt...

> on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier

are you serious? someone really asked you to "use array". Beyond stupid if they really did.

> you can easily blow the stack for real production grade implementations using recursion

recursive solution doesn't automatically mean using a the method stack. you can implement recursive solutions using explicit stack .

> dynamic programming proper

please. There is no "proper" dynamic programming. Please watch this MIT intro https://www.youtube.com/watch?v=OQ5jsbhAv_M .

It's not stupid to use an array, because it's the most natural data structure for representing one, two or more variables that can have different ranges and capturing their values.

For example, if I have a function 'foo(a, b, c)' and I am using subproblems whose solutions use smaller values of a, b, and c, then the most natural solution is to tabulate the solutions in a 3-d array with the (fixed) values of a, b, and c indexing into the 3-d array to get at the (solved) subproblem.

It's of course also fine to use a hash table to construct the triplet (a, b, c) and use it as the key to store (and look up) the solution to the subproblem that corresponds to the particular value of (a, b, c), and most reasonable interviewers would be happy to accept this as a valid approach.

As for recursive solutions automatically using the method stack, the overwhelming majority of programming languages provide the ability to do this, and the generally accepted understanding is that if you use this facility, you are using automatic recursion, letting the compiler/machine/runtime maintain the stack for you. The generally accepted terminology when you explicitly allocate your own stack is 'iterative'.

Also, the generally accepted terminology is 'Dynamic Programming' == 'Bottom-up tabulation', and 'Memoization' == 'Top-down recursion with caching to avoid solving the same subproblem'.

> are you serious? someone really asked you to "use array". Beyond stupid if they really did.

Google interview. Explicitly told me not to use recursion.

you're wrong on all counts but i'm going to be the one to correct you.

Nah, you're the one whose wrong on this one.

You both made some great points

I've solved some DP problems (I call it: "find the right table/array and then decide whether you feel recursive or iterative").

I know about lru caches.

Yet, I'm not fully understanding what your implying with your comment.

Op's saying (I think) that the difference between brute force recursion and DP ( top down ) is memoization, and that the language / library construct lru_cache will perform that memoization for you.

Its not a fascinating insight. If you can express a problem as a recursive brute force solution and there's a least a little recalculation involved, you're one step from DP. The lru_cache just does that step.

Just google lru_cache

edit: "op"

it is a particular part of the Python 3 standard library. it is one extra line of code to automatically memoize a recursive function.

you just do:

    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def brute_recursive_func(x):
        ...

And you're good to go.

Very nice! I often forget this handy thing during interviews. Good thing to impress your interviewer with :)

One thing of note: The arguments to the method you are memoizing need to be hashable. For example, if you want to memoize a method call whose parameters include a list, you will get an error!

DP is basically brute-force but you can reuse some of the subproblems.

Another approach is trying to find a "starting point" and solving subproblems. Imagine an array of problems and starting at the left.

>DP is basically brute-force but you can reuse some of the subproblems.

this is like saying

"integration is basically weighing a bunch of buckets but the buckets are really small"

cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

I don't think the comparison is accurate. The subproblem explanation of DP immediately lends itself to a strategy for solving problems: come up with a brute force solution then look for where you are duplicating where, i.e., how can a hash table help me? Even if there is a more efficient way to do things in the end than a hash table, I find it easier to go from brute force, to hash table, then finally look at it and see if I can optimize it further.

> "integration is basically weighing a bunch of buckets but the buckets are really small"

> cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

I am a mathematician and teacher of mathematics.

Understanding the first point is way more valuable than teaching the second. I have to ask and grade trigonometric-substitution problems for my Calculus II class because the curriculum includes it, but I'd way rather have a student come out of my class with a solid understanding of why your quoted statement about integration is true than to be able to find just the right substitution but have no idea why. They can look up the trigonometric-substitution stuff when they need it.

But we're not talking about hypothetical pedagogy here. Exams cover usub and trig sub and methods of partial fractions. In fact we're not even talking about calc at all but software interviews, which, like or it not, examine tricks.

That's exactly how I approach these problems: I think that's a hard problem so how about just a brute force solution first to validate correctness? Then a few minutes later you realize the repeated subproblem structure and turn brute force into DP.

I’m currently working through Leetcode now. I’m really taking the time to understand the various solutions with the goal of bettering myself as a software engineer. It’s honestly just fun working on the problems.

Anyways, did you get the FB job?

>Anyways, did you get the FB job?

Yup

It should be noted that FB stopped using DP problems in interviews for this very reason (they measure how much you've practiced rather than innate intelligence).

They can even come up completely outside of work. I recently had an optimization problem come up around the house that could have been straight out of an exam. Here it is:

Tzs wants to install gutter guards on his house and detached garage. His garage has two 29' straight gutters, and his house has two straight gutters of 43' and 19', and one L-shaped gutter with arms of 19' and 18'.

The guards tzs is going to use [1] are available from Home Depot in 3 ft and 4 ft sections. The 3 ft ones are sold in boxes of 13 for $79.97. The 4 ft ones are sold in boxes of 20, 10, or 3 for $139.97, $99.97, or $39.16.

To cover a gutter, you need slightly more length of guard than length of gutter. You cut off the rails on the end of the guards at the ends of the gutter, leaving a few inches of mesh that you can tuck down into the gutter to keep stuff from getting in through the ends. Assume that the section you cut off is waste.

Question 1: What boxes of guards should tzs buy to cover all his gutters for minimum cost, assuming he needs 3" of mesh at the ends to cover the sides? For the L shaped gutter, assume it effectively has 3 ends.

Question 2: The only ladder tzs has is a 6 ft step ladder. This is sufficient for installing the guards on the front side of his garage. It is not sufficient for anyplace else. To do the rest of the house, at a level of ladder safety he is comfortable with, will require buying at least one new ladder for $260, and might require a second new ladder for $129. Before committing to that, he is considering doing a test on the front of the garage.

If he buys one 13 pack and uses 10 of them on the front of garage, and then decides from there to go ahead with doing all the rest, what boxes should he then buy to finish the project taking into account the 3 leftover 3 ft segments? How much, if any, does this add to the minimum total project cost?

Question 3: the prices given earlier were actually sale prices for the 20 pack and 13 pack. If they go back to normal prices, which are $160.97 and $88.83, how does that change things?

Question 4: Due to rapidly sloping ground behind the garage, tzs has not been able to figure out a way to reach more than about half the gutter there. He is thinking of just not bothering with it. There are a lot of weeds and wildflowers and such in that area, so it doesn't really actually matter much if the gutters are clogged and the water just runs off the edge--it will just land on plants so won't erode the soil, and there is no basement or crawlspace under the garage for the water to leak into.

How do all the previous answers chance if the back garage gutter is omitted? If tzs figures out a way to actually reach the damn thing later, what will be the incremental cost to add that?

Question 5: When you cut an end segment, sometimes the waste piece can be significant. For example, suppose you have 1 ft to cover at the right end of a gutter and use a 3 ft segment. You might cut that segment 1 ft from the left end, and cut the mesh 4" to the right of that to get the mesh flap to fold over the gutter end. That leaves you with a 2ft segment with 4" of missing mesh. You could cut the rails 4.5" from the left of that (4.5" rather than 4" because the mesh needs to be slightly longer than the segment to overlap the adjacent segment). That would leave with a 1.75' segment that could be used just like any other segment.

Can you adapt your algorithm for finding minimal cost to take into account these small, usually non-integral, segments that would be produced as a by product of dealing with gutter end points?

Question 6: Can you adapt your algorithm to handle the possibility of purposefully breaking a long segment down into shorter segments, with the algorithm determining the optimal set of short segments to make? Assume that at each place you split a segment you loss 1" of total length due to the need for overlapping adjacent meshes.

[1] https://www.gutterglove.com/