Hello guys, I've been around for a month or so, and I have a very specific trouble when approaching a new problem if this one is unclear to me. I think this has has to be quite common and I was wondering if someone could help me a little bit.
The thing is, when I see a new problem and I don't have this flash solution (knowing exactly how to resolve it at first glance) I hesitate a lot and never start to do something. Why? Because I always think that there has to be a better time complexity solution than whatever I'm thinking about.
For instance, if I see some subarray-like problem, I know it's relatively easy to come up with a O(n^2) solution even if not an expert (of course this depends on the problem, but you get the idea). Though I think: this s__t is doable in O(n) with a DP solution pretty sure. Even O(nlogn) isn't enough (sorting first usually helps right).
On the other hand, we know that in a real situation in which you're getting tested, doing something is always better than looking at the screen waiting for a miracle idea.
So we can have two concrete questions from this:
- Is there any way to know the upperbound time optimal solution? Not the solution itself, just the best potential time complexity. I'm struggling when trying to identify DP problems for example. And f__k, it's a very big deal getting O(n) when the other choice is some exponential recursive trash.
- If not (probably), what to do? It's so frustrating when you spend that much time just to get TLE.
And also, I have let's say good CS background. Those stacks, queues, BT, etc weren't hard. But oh mate, I'm stuck with DP. It's like I can't learn it. Something in my brain doesn't work when dealing with DP, even with easy tagged problems. Any pointers? Errichto is too clever for me to follow up, and MIT lectures (Intro to Algo) on this subjects are superficial.
Thank you guys, it's my first post here in general, be gentle.