3 ms·

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 a

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.

anon_tor_12345 5y ago
>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.
- slaymaker1907 5y ago
  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.
- JadeNB 5y ago
  > "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.
  - anon_tor_12345 5y ago
    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.
kccqzy 5y ago
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.

anon_tor_12345 5y ago

>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.

slaymaker1907 5y ago
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.
JadeNB 5y ago
> "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.
- anon_tor_12345 5y ago
  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.

kccqzy 5y ago

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.