I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - should I use brute force or greedy search would work better or maybe dynamic programming would do the job? Then I start coding a solution just too find out it does not work and I have to pick another method.

I wonder if there is a way to restate the problem in some abstract way and from there to see what solution technique would work for it?

  • 1
    $\begingroup$ Problem solving is open-ended. $\endgroup$ – Yuval Filmus Aug 23 '20 at 11:19
  • $\begingroup$ @YuvalFilmus hard to argue with that. What I'm looking for is a guidance on how to recognise that a problem can be efficiently solved with a method or reject a method for a given problem. $\endgroup$ – averbin Aug 23 '20 at 11:43
  • 2
    $\begingroup$ 1) Experience. There are tons of approaches, but with some experience, you would "feel" when they are applicable. 2) Prove correctness before coding. "start coding a solution just too find out it does not work" should be a rare exception. And understanding why it fails can point towards solution. 3) Try a number of small examples. Usually, you can find some patterns from them, which point towards solution. 4) For greedy/dp: write your recursive function on the paper: it simplifies writing it as a code, and it's much simpler to prove that it's correct when it's in front of you. $\endgroup$ – user114966 Aug 23 '20 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.